Press "Enter" to skip to content

计算几何基础之“玻璃球”

思路1:暴力判断(数据比较弱)
思路2:叉积


#include<bits/stdc++.h> using namespace std; struct node{ int x,y; }; struct Line{ node a,b; }line[5005]; int n,m,ans[5005]; int cross(node p1,node p2,node p3) { return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y); } void judge(node d) { int i; for(i=0;i<n;++i) if(cross(line[i].b,d,line[i].a)<=0) { ans[i]++; return; } else continue; ans[n]++; return; } int main() { int i; node l,r,tmp; scanf("%d%d%d%d%d%d",&n,&m,&l.x,&l.y,&r.x,&r.y); memset(ans,0,sizeof(ans)); for(i=0;i<n;++i) { scanf("%d%d",&line[i].a.x,&line[i].b.x); line[i].a.y=l.y; line[i].b.y=r.y; } for(i=0;i<m;++i) { scanf("%d%d",&tmp.x,&tmp.y); judge(tmp); } for(i=0;i<=n;++i) printf("%d: %d\n",i,ans[i]); return 0; }

Be First to Comment

发表评论

电子邮件地址不会被公开。