POJ 2668 Game of Lines
发布日期:2022-02-05 18:27:27 浏览次数:14 分类:技术文章

本文共 1745 字,大约阅读时间需要 5 分钟。

Game of Lines
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 5923   Accepted: 2198

Description

Farmer John has challenged Bessie to the following game: FJ has a board with dots marked at N (2 ≤ N ≤ 200) distinct lattice points. Dot i has the integer coordinates Xi and Yi (-1,000 ≤ Xi ≤ 1,000; -1,000 ≤ Yi ≤ 1,000).

Bessie can score a point in the game by picking two of the dots and drawing a straight line between them; however, she is not allowed to draw a line if she has already drawn another line that is parallel to that line. Bessie would like to know her chances of winning, so she has asked you to help find the maximum score she can obtain.

Input

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 describes lattice point i with two space-separated integers: Xi and Yi.

Output

* Line 1: A single integer representing the maximal number of lines Bessie can draw, no two of which are parallel.

 

Sample Input

4-1 1-2 00 01 1

Sample Output

4

Source

USACO 2008 February Silver
看数据范围200 可以N^2枚举两点求斜率
一开始担心过double的精度问题 还想写gcd求出互质的△x和△y存起来
不过想到可能出负数  还是写double扔到set里吧
#include
#include
#include
#include
using namespace std;struct self{int x,y;}s[40044];int m,a,b,c,z;set
q;bool zero=0;bool ok(int x1,int y1,int x2,int y2){ int x=x1-x2; int y=y1-y2; if(x==0) { if(!zero) { zero=1; return true; } return false; } if(q.insert(double(y)/x).second)return true; return false;}int main(){ scanf("%d",&m); for(a=1;a<=m;a++)scanf("%d%d",&s[a].x,&s[a].y); for(a=1;a<=m;a++) for(b=a+1;b<=m;b++) if(ok(s[a].x,s[a].y,s[b].x,s[b].y))z++; cout<
<<'\n'; return 0;}

转载地址:https://blog.csdn.net/li412302070/article/details/12874325 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:最小奖励 MINAW
下一篇:POJ 3623 Best Cow Line

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年04月25日 01时58分42秒