COGS2090 Asm.Def找燃料

时间限制：1 s 内存限制：256 MB

【题目描述】

“听说咱们要完了？”比利·海灵顿拨弄着操纵杆，头也不回地问Asm.Def。

“不要听得风就是雨。”

“开个玩笑嘛。不就是打机器人，紧张啥，你看人家凯尔·里斯，还能顺便谈个恋爱……”

这时空天飞机陡然抬起机头， Asm.Def被紧紧压在座椅上。不一会，仪表盘上的青蛙玩偶飞了起来，表明他们已经进入近地轨道。

“华莱士比你还紧张，听说是要去什么无……”

“无线电焦点，在那能监听到透明计算网络控制的所有卫星。而且是已经去过了，所以我才会在这儿。”Asm.Def回答。

“这我知道，送你去拉格朗日点，你们的‘蓝翔’号星舰，只是有个小问题：没油了。”

“什么？！”

“我们可以去废弃卫星上找燃料。现在就差一个程序员。”

我们把太空看做一个二维平面。有N颗废弃卫星，第i颗的坐标是(xi,yi)。Asm.Def希望从尽可能多的卫星获取燃油，但他乘坐的空天飞机的飞行路径只能是一条直线，Asm.Def需要知道，这条直线最多能经过多少颗卫星。

【输入格式】

第1行1个整数N。

接下来N行，每行两个整数xi,yi，表示第i颗卫星的坐标。

【输出格式】

一行一个整数，即一条直线最多能经过多少颗卫星。

【样例输入】

【样例输出】

【提示】

对于30%的数据，1<=N<=10.

对于100%的数据，1<=N<=100，坐标为整数，绝对值<=10000.

写水题舒缓一下心情

数学问题计算几何暴力

这系列的题，题面都好神啊……

看了看数据范围，暴力怼过去好了。

$O(n^2)$枚举两点，然后$O(n)$判有多少点在线上

完毕

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 const double eps=1e-;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct point{

     double x,y;

     point operator + (point b){return (point){x+b.x,y+b.y};}

     point operator - (point b){return (point){x-b.x,y-b.y};}

     double operator * (point b){return x*b.x+y*b.y;}

 }a[mxn];

 double Cross(point a,point b){return a.x*b.y-a.y*b.x;}

 int ans=;

 int n;

 void solve(point st,point ed){

     int res=;

     for(int i=;i<=n;i++){

         if(fabs(Cross(a[i]-st,ed-st))<eps && ((a[i]-st)*(a[i]-ed)<=))res++;

     }

     ans=max(ans,res);

 }

 int main(){

     freopen("asm_fuel.in","r",stdin);

     freopen("asm_fuel.out","w",stdout);

     int i,j;

     scanf("%d",&n);

     for(i=;i<=n;i++)

         scanf("%lf%lf",&a[i].x,&a[i].y);

     for(i=;i<=n;i++){

         for(j=;j<=n;j++){

             if(i==j)continue;

             solve(a[i],a[j]);

         }

     }

     cout<<ans<<endl;

     return ;

 }

巴特西