WOJ1087-数星星输入格式输出格式样例输入样例输出

121 阅读 0 评论 80 点赞

我是靠谱客的博主冷傲大米，这篇文章主要介绍WOJ1087-数星星输入格式输出格式样例输入样例输出，现在分享给大家，希望可以做个参考。

一天，小希坐在院子里数星星，Gardon就出了个难题给她，让她数数天上的星星最多有多少个是在同一条直线上的。天上的星星太多了，小希马上就看花了眼，你能写个程序来帮她计算么？

输入格式

输入包含多组数据，每组数据的开头是一个整数N(N<=300)，接下来的N对数每对表示一个星星的位置（星星的坐标在-10000到10000之间，精确到小数点后1位）。没有两个星星会在同一个位置。

输出格式

一个整数，表示一条直线上最多星星的数目。

样例输入

复制代码

样例输出

复制代码

1
3

暴力枚举

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
struct P  
{  
    float x,y;  
}a[301];
int main()  
{  
    int n;  
    while(scanf("%d",&n)!=EOF&&n!=0)  
    {  
        for(int i=0;i<n;i++)  
            scanf("%f %f",&a[i].x,&a[i].y);  
        int ans=1;  
        for(int i=0;i<n;i++)  
        {  
            for(int j=i+1;j<n;j++)  
            {  
                int sum=2;  
                for(int k=j+1;k<n;k++)  
                {  
                    if((a[i].x-a[j].x)*(a[j].y-a[k].y)==(a[j].x-a[k].x)*(a[i].y-a[j].y))  
                        sum++;  
                }  
                if(sum>ans) ans=sum;  
            }  
        }  
        printf("%dn",ans);  
    }
	return 0;  
}