列表

详情


NC212850. 鸽者文明的三体问题

描述

在鸽者文明使用二项箔降维打击之后,整个宇宙都平面化了,不仅维度降低了,在二维世界中引力模式也产生了改变,只有特定的星球围成的三角形区域内才会产生引力,一个区域如果被上述三角形区域奇数次覆盖(1,3,5...)则有引力存在,而如果一块区域内被不同的三角区域覆盖偶数次(0,2,4...)则他们之间的引力作用就被抵消了(相当于没有引力),为了更好的适应二维世界,鸽者文明知名学者-鸽伽尊,提出了伟大的鸽者文明的三体问题,给出n个已知的能产生引力的星球组坐标(一组坐标包含3个星球,一个星球坐标计为(xi,yi)),然后有q组询问,每次询问一个位置(xqi,yqi),这个点是否存在引力(被抵消等同没有引力),如果有引力则输出"Yes"(没有引号),不然输出"No"(没有引号)

输入描述

第一行跟着2个整数n,q ,分别代表已知的能产生引力的星球组数,以及询问数,之后跟着3n行,每一行包含两个整数  ,代表一个星球的坐标,第k+1,第k+2,第k+3星球组成的三角形内(包括边界)存在引力(k=0,3,6...)题目保证每一组的三个星球不会在同一直线上且组内不会有星球重叠(保证构成三角形)。之后跟着q行询问,每次询问给出2个整数,表示询问的地点的坐标,每次询问给出对应的答案,题目保证询问的点不会刚好在三角区域的顶点或边上。

输出描述

输出q行,每一行仅有"Yes"或"No",代表第k次询问的结果

示例1

输入:

2 3
1 0
4 0
1 2
5 0
0 0
1 3
2 1
2 2
2 3

输出:

No
Yes
No

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C 解法, 执行用时: 9ms, 内存消耗: 372K, 提交时间: 2022-10-18 22:39:56

#include<stdio.h>
int main()
{
	int n,q;
	scanf("%d %d",&n,&q);
	int a[3*n][2],b[2],c[4][2],i,t,x,y,z;
	for(i=0;i<n;i++){
		scanf("%d %d",&a[3*i][0],&a[3*i][1]);
		scanf("%d %d",&a[3*i+1][0],&a[3*i+1][1]);
		scanf("%d %d",&a[3*i+2][0],&a[3*i+2][1]);
	}
	while(q--){
		scanf("%d %d",&b[0],&b[1]);
		t=0;
		for(i=0;i<n;i++){
			c[1][0]=a[3*i][0]-b[0];
			c[1][1]=a[3*i][1]-b[1];
			c[2][0]=a[3*i+1][0]-b[0];
			c[2][1]=a[3*i+1][1]-b[1];
			c[3][0]=a[3*i+2][0]-b[0];
			c[3][1]=a[3*i+2][1]-b[1];
			x=c[1][0]*c[2][1]-c[1][1]*c[2][0];
			y=c[2][0]*c[3][1]-c[2][1]*c[3][0];
			z=c[3][0]*c[1][1]-c[3][1]*c[1][0];
			if((x>=0&&y>=0&&z>=0)||(x<0&&y<0&&z<0))t++;
		}
		if(t%2)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

C++(clang++11) 解法, 执行用时: 18ms, 内存消耗: 504K, 提交时间: 2020-11-04 23:43:40

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n ,q;	

struct p{
	double x,y;
}a[1005][3];
double area(p a1,p a2,p a3){
p  A,B;
	 A.x=a2.x-a1.x;
	 A.y=a2.y-a1.y;
	 B.x=a3.x-a1.x;
	 B.y=a3.y-a1.y;
	return abs((A.x*B.y-B.x*A.y))/2.0;
	
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	for(int j=0;j<3;j++)
       cin>>a[i][j].x>>a[i][j].y;
	for(int i=1;i<=q;i++){
		int ans=0;p xx;
	     cin>>xx.x>>xx.y;
		for(int j=1;j<=n;j++){	
		double sum=0,k=0;
	 sum=area(a[j][0],a[j][1],a[j][2]);
	k=area(xx,a[j][1],a[j][2])+area(a[j][0],xx,a[j][2])+area(a[j][0],a[j][1],xx);
	   if(k<=sum)ans++;
		} 
		if(ans%2==0)cout<<"No";
		else cout<<"Yes";
		cout<<endl;
	}
	return 0;
}

上一题