专栏文章

abc422_e题解

ccyq32ent
AT_abc422_d题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minze560
此快照首次捕获于
2025/12/02 10:51
3 个月前
此快照最后确认于
2025/12/02 10:51
3 个月前
查看原文
随机选取两个点，则这两个点过所求直线的概率，即这两个点在直线经过的点集 SS 中的概率。由于我们假定 ∣S∣>N2|S|>\frac N2，所以这个概率不小于 14\frac14。进行 5050 次测试，则误判的概率为 5.66×10−75.66\times 10^{-7} 左右，如果 5050 次测试均不通过，可以认为这不存在这样一条直线。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int N,x[514514],y[514514];
void check(int i,int j){
	int a=y[j]-y[i],b=x[i]-x[j],c=x[j]*y[i]-x[i]*y[j],cnt=0;
	for(int _=1;_<=N;_++)if(a*x[_]+b*y[_]+c==0)cnt++;
	if(cnt>=N/2+1)cout<<"Yes\n"<<a<<' '<<b<<' '<<c,exit(0);
}
signed main(){
	mt19937 rnd(time(0));
	cin>>N;for(int i=1;i<=N;i++)cin>>x[i]>>y[i];
	for(int _=0;_<50;_++){
		int i=rnd()%N+1,j=rnd()%N+1;if(j==i)j=(i)%N+1;
		check(i,j);
	}cout<<"No";
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...