#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 月银牌组