NC212850. 鸽者文明的三体问题
描述
输入描述
第一行跟着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; }