uva 270 Lining Up

发布时间:2016-12-8 4:12:56 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"uva 270 Lining Up",主要涉及到uva 270 Lining Up方面的内容,对于uva 270 Lining Up感兴趣的同学可以参考一下。

题意:问你若干个点中最多有几个在同一条直线上,那么我们先确定一条直线,然后再一一找就好了,在同一直线的条件是斜率相同,我们把它转化成等式的形式,就能避免误差了,至于怎么选点的方法就跟组合一个意思#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int MAXN = 750 ; struct node { int x,y; }arr[MAXN]; int nIndex; char str[1000]; void input() { nIndex = 0 ; while (gets(str)) //gets()将'\n'变成 '\0' { if (!str[0]) break; sscanf(str,"%d%d",&arr[nIndex].x,&arr[nIndex].y); nIndex++; } } bool is_in_line(int x1,int y1,int x2,int y2,int x3,int y3) { return ((x1-x2)*(y3-y2)-(x3-x2)*(y1-y2))==0; } void solve() { int nmax = 2; for (int i = 0 ; i < nIndex; i++) { for (int j = i+1 ; j < nIndex; j++) { int cnt = 2; for (int k = j+1 ; k < nIndex; k++) { if (is_in_line(arr[i].x,arr[i].y,arr[j].x,arr[j].y,arr[k].x,arr[k].y) ) cnt++; } if (cnt > nmax) nmax = cnt; } } printf("%d\n",nmax); } int main() { int T; scanf("%d",&T); getchar(); gets(str); while (T--) { input(); if (nIndex == 1) printf("1\n"); else if ( nIndex == 2 ) printf("2\n"); else solve(); if (T) printf("\n"); } return 0; }

上一篇:桌子上放硬币
下一篇:import javax.servlet.annotation.WebServlet

相关文章

关键词: uva 270 Lining Up

相关评论