这道题才真的没有那么的水,可能因为测试数据很多,然后又每个数据有1000个点要处理,用O(n^3)的三重循环直接TLE掉了。。。
所以得另想办法,后来参考了一下别人的想法,得用极角排序,一个sort()就可以了,极角为0的因为无法做分母,所以得单独考虑,终于AC。。。
AC的代码:
#include <stdio.h> #include <iostream> #include <algorithm> using namespace std; int x[1002],y[1002]; int main() { int n; int i,j,k,max; while(scanf("%d",&n)!=EOF) { //输入 for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); max=2; //每次循环都判断 for(k=1;k<=n;k++) { int count1=1; double angle[1002]; int zero=0; for(i=1;i<=n;i++) { //单独处理分母为0的情况 if(x[i]-x[k]==0) zero++; else angle[count1++]=(double)(y[i]-y[k])/(double)(x[i]-x[k]); } //按极角的大小进行排序 sort(&angle[1],&angle[count1]); //看排序的里面有几个连续的数 int temp=2; int sum=2; double pos=angle[1]; for(i=2;i<count1;i++) { //是相同的就count++ if(pos==angle[i]) sum++; //否则就重头开始计数 else { pos=angle[i]; if(sum>temp) temp=sum; sum=2; } } if(temp>max) max=temp; if(zero>max) max=zero; } printf("%d\n",max); } return 0; }
TLE的代码:
#include <stdio.h> int x[1002],y[1002]; int main() { int n; while(scanf("%d",&n)!=EOF) { int i; //输入坐标点的值 for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); //暴搜开始 int count,max=-1; int j,k; for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) { count=2; for(k=j+1;k<=n;k++) if((y[i]-y[k])*(x[j]-x[k])==(y[j]-y[k])*(x[i]-x[k])) count++; if(max<count) max=count; } printf("%d\n",max); } return 0; }
时间: 2024-11-30 18:09:57