#P3668. Game of Lines
Game of Lines
题目描述
农夫约翰向贝茜发起了如下挑战:约翰有一块木板,上面标有 N 个(2 ≤ N ≤ 200)不同的格点。第 i 个点的坐标为整数 (Xi, Yi)(-1,000 ≤ Xi ≤ 1,000;-1,000 ≤ Yi ≤ 1,000)。
贝茜在游戏中可以通过选择两个点并在它们之间画一条直线来得分,但 如果她已经画过一条与之平行的直线,则不允许再画这条线。贝茜想知道自己的获胜机会,因此请你帮忙计算她能获得的 最大得分(即最多能画多少条互不平行的直线)。
输入格式
- 第 1 行:一个整数 N
- 第 2 行至第 N+1 行:每行两个空格分隔的整数 Xi 和 Yi,表示第 i 个格点的坐标
输出格式
- 第 1 行:一个整数,表示贝茜能画出的互不平行的直线的最大数量
输入输出样例
输入数据 1
4
-1 1
-2 0
0 0
1 1
输出数据 1
4
题目来源
USACO 2008 年 2 月银牌组