emmm.......随机化。
好吧,我们不熟。
考虑随机选取两组数据高斯消元消除结果后带入检验,能有超过1/2正确就输出。
其实方程就四个,手动解都没问题。
只是要注意看sin与cos的关系来确定角象限,被这个卡掉了,挑了好久。
还要注意在合适的情况下\(eps\)越大越好。
Code
#include<bits/stdc++.h>
using namespace std;
namespace STD
{
#define rr register
#define scanf ybbb=scanf
#define x1 a[id1].X1
#define x2 a[id2].X1
#define y1 a[id1].Y1
#define y2 a[id2].Y1
#define x1_ a[id1].X2
#define x2_ a[id2].X2
#define y1_ a[id1].Y2
#define y2_ a[id2].Y2
typedef long long ll;
const int N=1e5+5;
const double e=1e-4;
int n,ybbb ;
struct line{double X1,X2,Y1,Y2;} a[N];
int read()
{
rr int x_read=0,y_read=1;
rr char c_read=getchar();
while(c_read<'0'||c_read>'9')
{
if(c_read=='-') y_read=-1;
c_read=getchar();
}
while(c_read<='9'&&c_read>='0')
{
x_read=(x_read<<3)+(x_read<<1)+(c_read^48);
c_read=getchar();
}
return x_read*y_read;
}
bool check(double cos,double sin,double dx,double dy)
{
int cnt=0;
for(rr int i=1;i<=n;i++)
{
double x_=cos*a[i].X1-sin*a[i].Y1+dx;
double y_=cos*a[i].Y1+sin*a[i].X1+dy;
if(fabs(x_-a[i].X2)<=e&&fabs(y_-a[i].Y2)<=e)
cnt++;
}
return cnt>=((n+1)>>1)&&cnt<=n;
}
};
using namespace STD;
int main()
{
n=read();
for(rr int i=1;i<=n;i++)
scanf("%lf%lf%lf%lf",&a[i].X1,&a[i].Y1,&a[i].X2,&a[i].Y2);
double x,b,c,d,scale,cos,sin;
srand(time(0));
for(rr int i=1;i<=500;i++)
{
int id1=rand()%n+1;
int id2=rand()%n+1;
while(id1==id2) id2=(id2-rand()%n+n)%n+1;
x=x1_-x2_-(y1_-y2_)*(y2-y1)/(x1-x2);
x=x/(x1-x2+(y1-y2)*(y1-y2)/(x1-x2));
b=((y1_-y2_)-(x*(y1-y2)))/(x1-x2);
c=(x1_-x*x1+b*y1);d=(y1_-b*x1-x*y1);
if(!check(x,b,c,d))continue;
scale=sqrt(x*x+b*b);
cos=x/scale,sin=b/scale;
break;
}
printf("%.7lf\n%.7lf\n%.7lf %.7lf\n",sin>0?acos(cos):-acos(cos),scale,c,d);
}