bzoj 4814: [Cqoi2017]小Q的草稿【计算几何】

//先打个50暴力,10min50分简直美滋滋~

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=5005;

const double eps=1e-8;

int n,t,m,ans;

struct dian

{

	double x,y;

	dian(double X=0,double Y=0)

	{

		x=X,y=Y;

	}

	dian operator + (const dian &a) const

	{

		return dian(x+a.x,y+a.y);

	}

	dian operator - (const dian &a) const

	{

		return dian(x-a.x,y-a.y);

	}

}a,b,c,p[N];

struct bian

{

	dian s,t;

	bian(dian S=dian(),dian T=dian())

	{

		s=S,t=T;

	}

}l[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int sgn(double x)

{

	return x<-eps?-1:x>eps;

}

double cj(dian a,dian b)

{

	return a.x*b.y-a.y*b.x;

}

bool lc(dian a,dian b,dian c,dian d)

{

	return sgn(cj(c-a,b-a)*cj(b-a,d-a))>=0;

}

bool jiao(dian a,dian b,dian c,dian d)

{

	return lc(a,b,c,d)&&lc(c,d,a,b);

}

bool ok(dian a,dian b)

{

	for(int i=1;i<=m;i++)

		if(jiao(a,b,l[i].s,l[i].t))

			return 0;

	return 1;

}

int main()

{

	n=read(),t=read();

	for(int i=1;i<=n;i++)

		p[i].x=read(),p[i].y=read();

	for(int i=1;i<=t;i++)

	{

		a.x=read(),a.y=read(),b.x=read(),b.y=read(),c.x=read(),c.y=read();

		l[++m]=bian(a,b),l[++m]=bian(b,c),l[++m]=bian(c,a);

	}

	for(int i=1;i<=n;i++)

		for(int j=i+1;j<=n;j++)

			if(ok(p[i],p[j]))

				ans++;

	printf("%d\n",ans);

	return 0;

}
巴特西

bzoj 4814: [Cqoi2017]小Q的草稿【计算几何】

最新文章

热门文章
