914
hdu 1756 Cupid's Arrow 計算幾何
判斷點是否在多邊形內部
對於任意四邊形，可以隨機選取一條射線向外延伸，如果相交邊數為奇數，則在內，偶數，則在外
這題無需考慮在邊上的情況
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
給定n個點的坐標，這n個點依次圍成一閉合多邊形，再給一點（x，y），判斷它是否在多邊形中。
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 1E9
#define eps 1e-8
using namespace std;
struct Node
{
double x,y;
};
Node org[1000005];
Node A,B;
int n,i;
double cross(Node A, Node B, Node C)
{
return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}
bool isZero(double x) {//判斷x是否接近0
return (x > 0 ? x : -x) < eps;
}
bool in()
{
int count, i = 0;
org[n] = org[0];
while (i < n)
{
B.x = rand() + INF; //隨機取一個足夠遠的點B
B.y = rand() + INF; //以A為起點B為終點做射線L
for (i=count=0; i<n; ++i)
{
/*
if (isZero(cross(A,org[i],org[i+1]))&&
(org[i].x-A.x)*(org[i+1].x-A.x)<eps&&(org[i].y-A.y)*(org[i+1].y-A.y)<eps)
return 0;//點A在邊上
*/
if (isZero(cross(A, B, org[i]))) break;//點org[i]在射線AB上，停止本循環，另取B
else if (cross(org[i], org[i+1], A)*cross(org[i], B, org[i+1])>eps &&//射線與邊相交，統計交點數
cross(A, B, org[i])*cross(A, org[i+1], B)>eps) ++count;
}
}
return count & 1;
}
int main()
{
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
{
scanf("%lf%lf",&org[i].x,&org[i].y);
}
int m;
scanf("%d",&m);
while(m--)
{
scanf("%lf%lf",&A.x,&A.y);
if(in())puts("Yes");
else puts("No");
}
}
}
最後更新：2017-04-03 18:52:17