记录编号	244467	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]新家	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.802 s
提交时间	2016-04-01 08:23:40	内存使用	0.37 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int SIZEN=1010;
typedef long long LL;
int N;
class poi
{
public:
	int x,y;
}P[SIZEN];
int gcd(int x,int y)
{
	if(!y) return x;
	return gcd(y,x%y);
}
class miku//线
{
public:
	int x1,y1,x2,y2;
	LL a,b,c;//直线方程
	bool flag;//斜率
	void push(poi g,poi f)
	{
		x1=g.x,y1=g.y,x2=f.x,y2=f.y;
		if(x1>x2) {swap(x1,x2);swap(y1,y2);}
		LL A=y2-y1,B=x2-x1;
		LL C=gcd(A,B);
		A/=C;B/=C;
		if(B<0) A*=(-1),B*=(-1);
		a=A;c=B;b=B*y1-A*x1;
		if(y1>y2) flag=1;
		else flag=0;
	}
	void print()
	{
		cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
		cout<<"a:"<<a<<" "<<"b:"<<b<<" "<<"c:"<<c<<endl;
		cout<<endl;
	}
}L[SIZEN];
int key[SIZEN];
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d%d",&P[i].x,&P[i].y),key[i]=P[i].x;
}
void prepare()
{
	for(int i=1;i<N;i++) 
		L[i].push(P[i],P[i+1]);
	L[N].push(P[N],P[1]);
	//for(int i=1;i<=N;i++) L[i].print();
}
pair<double,int> S[SIZEN*2];
bool cmp(miku a,miku b,int x1,int x2)
{
	LL A=(a.a*x1+a.b)/a.c;
	LL B=(b.a*x2+b.b)/b.c;
	if(A<=B) return 1;
	if(A>B+1) return 0;
	A=(a.a*x1+a.b)%a.c;
	B=(b.a*x2+b.b)%b.c;
	return (A*b.c-B*a.c)<0;
}
LL get(LL a,LL b,LL c,LL n)
{
	if(a<0) return get(-a,b+a*(n-1),c,n);
	if(!n) return 0;
	LL re=0;
	if(a>=c) re+=n*(n-1)/2*(a/c),a%=c;
	if(abs(b)>=c) re+=n*(b/c),b%=c;
	if(!a) return re;
	re+=get(c,(a*n+b)%c,a,(a*n+b)/c);
	return re;
}
LL get1(miku a,int x1,int x2)//向下取整
{
	LL re=get(a.a,a.b,a.c,x2+1);
	re-=get(a.a,a.b,a.c,x1);
	return re;
}
LL get2(miku a,int x1,int x2)//向上取整
{
	LL re=get(a.a,a.b+a.c-1,a.c,x2+1);
	re-=get(a.a,a.b+a.c-1,a.c,x1);
	return re;
}
LL Calc(miku a,miku b,int x1,int x2)//处理在直线a下，直线b上，横坐标在x1,x2之间的格子
{
	//将a上所有的点的y坐标向下取整，减去b上所有点的y坐标向上取整的结果，便是答案
	//由于a上的点是向下取整，b上的点事向上取整，所以会出现floor<ceil的情况
	//我们需要二分出来一个x，使得floor>=ceil
	if(cmp(a,b,x1+a.flag,x1+!b.flag))
	{
		int l=x1,r=x2;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(cmp(a,b,mid+a.flag,mid+!b.flag)) l=mid+1;
			else r=mid;
		}
		x1=r;
		if(x1>x2) return 0;
	}
	if(cmp(a,b,x2-!a.flag,x2-b.flag))
	{
		int l=x1,r=x2;
		while(l+1<r)
		{
			int mid=(l+r)/2;
			if(cmp(a,b,mid-!a.flag,mid-b.flag)) r=mid;
			else l=mid;
		}
		x2=l;
		if(x1>x2) return 0;
	}
	LL re=0;
	if(!a.flag) re+=get1(a,x1,x2-1);
	else re+=get1(a,x1+1,x2);
	if(!b.flag) re-=get2(b,x1+1,x2);
	else re-=get2(b,x1,x2-1);
	return re;
}
void work()
{
	sort(key+1,key+1+N);//离散化x坐标
    LL ans=0;
	for(int i=1;i<N;i++)
	{
		if(key[i+1]==key[i]) continue;
		int tot=0;
		for(int j=1;j<=N;j++)
		{
			if(L[j].x1<=key[i]&&L[j].x2>=key[i+1])
				S[++tot]=make_pair((double)(L[j].a*(double)(key[i+1]+key[i])/2.0+L[j].b)/L[j].c,j);
		}
		sort(S+1,S+1+tot);
		for(int j=1;j<=tot;j+=2)
		{
			LL tem=Calc(L[S[j+1].second],L[S[j].second],key[i],key[i+1]);
			ans+=tem;		
		}
	}
	printf("%lld\n",ans);
}
int main()
{
	freopen("nt2011_zej_c.in","r",stdin);
	freopen("nt2011_zej_c.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}