?

大意：判斷最多有多少點在同一直線上。

思路：可以通過枚舉所有點加判斷三點共線去解決，即(y2-x1) /(x2-x1) = (y3-y1)/(x3-x1);

注意輸入格式比較特別。

CODE：

?

#include?<iostream>
#include?<cstdlib>
#include?<cstring>
#include?<cstdio>
#include?<algorithm>
#include?<cmath>
#include?<map>
using?namespace?std;

#define?MAXN?10001

int?x[MAXN],?y[MAXN];
int?tot;

void?init()
{
????tot?=?0;
????memset(x,?0,?sizeof(x));
????memset(y,?0,?sizeof(y));
}

void?solve()
{
????int?Max?=?1,?kMax;
????for(int?i?=?0;?i?<?tot;?i++)
????{
????????for(int?j?=?i+1;?j?<?tot;?j++)
????????{
????????????int?k1?=?x[j]-x[i],?k2?=?y[j]-y[i];
????????????kMax?=?2;
????????????for(int?k?=?j+1;?k?<?tot;?k++)
????????????{
????????????????int?k3?=?x[k]-x[j],?k4?=?y[k]-y[j];
????????????????if(k2*k3?==?k1*k4)
????????????????{
????????????????????kMax++;
????????????????}
????????????}
????????????Max?=?max(Max,?kMax);
????????}
????}
????printf("%d\n",?Max);
}

int?main()
{
????char?str[110];
????int?T;
????scanf("%d%*c",?&T);
????getchar();
????while(T--)
????{
????????init();
????????while(gets(str))
????????{
????????????if(!str[0]?&&?tot)?break;
????????????sscanf(str,?"%d%d",?&x[tot],?&y[tot]);?
????????????tot++;
????????}
????????solve();
????????if(T)?printf("\n");
????}
????return?0;
}

轉載于:https://www.cnblogs.com/g0feng/archive/2012/10/15/2724381.html

總結

以上是生活随笔為你收集整理的UVA 270 Lining Up的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。