2028. 妹妹的饼干

【题目描述】

long long ago one day，你的妹妹放假回家，由于你的妹妹长期住校，你们很少有机会接触。

你兴奋的不得了，可是妹妹却说她要跟本子哥CH一起度过整个暑假。

你立即央求妹妹，妹妹说：我这里有一个考验，如果你能通过，我就跟你呆在一起。

从蓝翔毕业的你，对一切考验都很有自信。

妹妹拿出了一个夹心饼干

“这是CH哥哥送我的夹心饼干！”

随后，妹妹胡乱的咬了几口饼干，饼干变成了格点多边形。(此时请不要想象妹妹的牙齿分布)

“现在，我给定被咬后饼干顶点的坐标，求最多能打多少个整口（小圆点）。”

已知小圆点必须位于整点上，这些坐标以逆时针或顺时针给出，饼干的边缘不能打点

真是个难题啊！你想来想去，可能会的人只有CH,于是你去找他，CH性情开朗，他说：你把你妹妹的高清照片发给我，我要出十个本子，我就帮你搞

你实在是迫不得已，答应了CH的hentai请求

十年之后，你又想起了这个问题，于是你决定去编程来解决这个问题。

【输入格式】

第一行一个整数n,表示坐标的个数

接下来每一行两个整数x,y

【输出格式】

一个整数m,表示最多有多少个整点

【样例输入】

3

1 1

4 2

2 3

【样例输出】

2

【样例解释】//By POWERPOINT

存在两个整点(2,2)和(3,2)

【提示】

对于40%的测试数据，1<=n<=10,abs(xi,yi)<=10^3

对于60%的测试数据，1<=n<=30,abs(xi,yi)<=10^5

对于80%的测试数据，1<=n<=40,abs(xi,yi)<=10^6,全是凸多边形

对于100%的测试数据，1<=n<=1024,abs(xi,yi)<=10^9，存在凹多边形

本题并不旨在考察选手对某一定理或某一知识点的了解能力，考察选手的判断能力和找规律能力，所以存在以下提示

线性关系：对于变量x1,x2,x3,....xn,存在常数a1,a2,a3....an使得

a1*x1+a2*x2+...an*xn=C(常数)

三角形的面积，三角形边上的整点，三角形内部的整点存在线性关系。

即设这三个变量分别为x,y,z存在常数A,B,C,D对于任意x,y,z都有Ax+By+Cz=D

1.WJX和嘉鑫属于化名，请不要联想到实际生活中的人物

2.看完本文后，请不要在实际生活中抢夺别人的妹妹或产生其他犯罪冲动

3.对于部分宅男请正视自己没有妹妹的现实

4.妹子图片选自pokemon XY，饼干图片选自百度。

5.搬运了【国家集训队2011新家】【COGS1898】的部分大号测试数据，受“新家”的一部分影响，但我不会做

【来源】