這道題可以算是1118,2780的升級(jí)版，因?yàn)楦菀壮瑫r(shí)了 O(∩_∩)O~
題目的意思很簡(jiǎn)單，給你許多點(diǎn)，然后讓你求出在同在一條直線上的點(diǎn)最多有多少個(gè)。
這道題做了2個(gè)小時(shí)，開(kāi)始用了暴搜的方法（那個(gè)方法不用考慮斜率不存在的情況），超時(shí)了，汗~后來(lái)改成計(jì)算斜率的方法才過(guò)的 方法如下：
單獨(dú)考慮斜率不存在的情況，把所有的點(diǎn)按照x的大小排序，算出x相同的點(diǎn)最多有多少個(gè)，保存到max1里；
然后考慮斜率存在的情況，考慮一個(gè)定點(diǎn)，把它和其它直線的斜率都算出來(lái)，排序，然后再計(jì)算相同的斜率最多有多少個(gè)，每個(gè)點(diǎn)都這樣算一遍，取最大值中的最大值，存在max2中；
最后比較max1和max2+1（注意max2我們是用斜率算的，它代表max2+1個(gè)點(diǎn)）取較大值輸出即可；
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node 
{
int x;
int y;
}set[1001];
int cmp(const void *a,const void *b)
{
struct node*c=(node *)a;
struct node*d=(node* )b;
return c->x-d->x;
}
char temp[100];
double slope[10001];
int main ()
{
int n;
int i,j,k;
int testcase;
testcase=0;
int max1;
int max2;
int pos;
int tempmax2;
for(testcase=1;;testcase++)
{
pos=0;
while(gets(temp))
{
if(temp[0]=='-'&&temp[1]=='-')
break;
pos++;
sscanf(temp,"%d%d",&set[pos].x,&set[pos].y);
}
n=pos;
if(n==0)
break;
int tempmax=1;
max1=0;
qsort(set+1,n,sizeof(set[1]),cmp);
for(i=2;i<=n;i++)
{
if(set[i].x!=set[i-1].x)
tempmax=1;
else
tempmax++;
if(tempmax>max1)
max1=tempmax;
}
max2=0;
for(i=1;i<=n;i++)
{
pos=0;
for(j=1;j<=n;j++)
{
if(i!=j&&set[i].x!=set[j].x)
{
pos++;
slope[pos]=((double)set[j].y-set[i].y)/((double)set[j].x-set[i].x);
}
}
sort(slope+1,slope+1+pos);
tempmax=1;
tempmax2=0;
for(j=2;j<=pos;j++)
{
if(slope[j]!=slope[j-1])
tempmax=1;
else
tempmax++;
if(tempmax>tempmax2)
tempmax2=tempmax;
}
if(tempmax2>max2)
max2=tempmax2;
}
if(max1>max2)
printf("%d. %d\n",testcase,max1);
else
printf("%d. %d\n",testcase,max2+1);
}
return 0;
}