Vasya and Cornfield CodeForces - 1030B

原题链接
考察:计算几何
思路:
  两种方法:
一:线性规划
(1) \(x-d<=y<=x+d\)
(2) \(-x+d<=y<=-x+2n-d\)

二:叉乘判别法(只适用于凸多边形)
  看这里GO
&emps; 没找到证明,但注意外积相乘不是累乘,只与上一个乘就行了.

Code(思路二)

#include <iostream> 
#include <cstring>
using namespace std;
int n,d,m;
int xx[4],yy[4];
int main()
{
	scanf("%d%d%d",&n,&d,&m);
	xx[0] = 0,xx[1] = d,xx[2] = n,xx[3] = n-d;
	yy[0] = d,yy[1] = 0,yy[2] = n-d,yy[3] = n;
	while(m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int pre = 1;
		bool ok = 1;
		for (int i = 0; i < 4;i++)
		{
			int a = xx[(i + 1) % 4] - xx[i], b = yy[(i + 1) % 4] - yy[i];
			int c = x - xx[i], d = y - yy[i];
			int res = a * d - b * c;
			if(i)
				pre = res * pre;
			if(pre<0)
				ok = 0;
			pre = res;
		}
		if(ok)
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}

上一篇:洛谷多校第5轮


下一篇:监控系统项目实施--安装与部署-PG数据库监控配置-libzbxpgsql部署