## 634 - Polygon

Moderator: Board moderators

anjanpstu
New poster
Posts: 7
Joined: Thu Apr 07, 2011 8:40 am

### 634 - Polygon

I am getting WA but cant understand

Code: Select all

``````#include<stdio.h>
int edgeType(int p_x,int p_y,int po_x0,int po_x1,int po_y0,int po_y1);
int pointClassify(int cp_x,int cp_y,int cpo_x0,int cpo_x1,int cpo_y0,int cpo_y1);
enum point {Outside,Inside,Boundary};
enum edge {Touching,Crossing,Inessential};
enum orientation{Left,Right,Between,Origin,Destination};
int main()
{
int poly_x[1000];int poly_y[1000];int point_x,point_y;int n;int parity=0;
//freopen("63.in","rb",stdin);
while(scanf("%d",&n)==1)
{
if(n==0)break;
else
{
parity=0;
for(int i=0;i<n;i++)
{
scanf("%d %d",&poly_x[i],&poly_y[i]);
}
scanf("%d %d",&point_x,&point_y);

for(int i=0;i<n-1;i++)
{
switch(edgeType(point_x,point_y,poly_x[i],poly_x[i+1],poly_y[i],poly_y[i+1]))
{
case Touching:
parity=0;
break;
case Crossing:
parity=1-parity;
break;
case Inessential:
parity=0;
break;
}
}
if(parity==1)
printf("T\n");
else
printf("F\n");
}
}
}

int edgeType(int p_x,int p_y,int po_x0,int po_x1,int po_y0,int po_y1)
{
switch(pointClassify(p_x,p_y,po_x0,po_x1,po_y0,po_y1))
{
case Left:
return ((po_y0<p_y)&&(p_y<=po_x1)) ? Crossing : Inessential;
break;
case Right:
return ((po_y1<p_y)&&(p_y<=po_y0)) ? Crossing : Inessential;
break;
case Between:
case Origin:
case Destination:
break;
default:
return Inessential;
break;
}
}

int pointClassify(int cp_x,int cp_y,int cpo_x0,int cpo_x1,int cpo_y0,int cpo_y1)
{
int a_x=cpo_x1-cpo_x0;int a_y=cpo_y1-cpo_y0;
int b_x=cp_x-cpo_x0;int b_y=cp_y-cpo_y0;
int sa=(a_x*b_y)-(b_x*a_y);
if(sa>0)
return Left;
else if(sa<0)
return Right;
else if(cpo_x0==cp_x&&cpo_y0==cp_y)
return Origin;
else if(cpo_x1==cp_x&&cpo_y1==cp_y)
return Destination;
else
return Between;
}
[size=85][/size]
``````

anjanpstu
New poster
Posts: 7
Joined: Thu Apr 07, 2011 8:40 am

### Re: 634 polygon WA

atlast got accepted somedays ago
solution:
case Left:
return ((po_y0<p_y)&&(p_y<=po_y1)) ? Crossing : Inessential;
break;

and check parity only for touching not otherwise

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 634 - Polygon

I am getting wrong answer for this problem.Can anyone figure out where is the problem?

Code: Select all

``````
#include <bits/stdc++.h>
#define EPS 1e-9
#define pi acos(-1)
using namespace std;

struct point
{
//***when points are double
double x,y,angle;
point()
{
x=0;
y=0;
angle=0;
}
//sort points first with respect to x then y
};

bool compare(point a,point b)
{
if(fabs(a.angle-b.angle)<EPS)
{
if(fabs(a.y-b.y)<EPS)
return a.x<b.x;
return a.y<b.y;
}
return a.angle<b.angle;
}

int orientation(point p, point q, point r)
{
// See 10th slides from following link for derivation of the formula
// http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);

if (val == 0) return 0;  // colinear

return (val > 0)? 1: 2; // clock or counterclock wise
}

bool onSegment(point p, point q, point r)
{
if(orientation(p,q,r)!=0)//not colinear
return false;
if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
return true;

return false;
}

bool inPolygon(point p,vector<point>P)
{
//assumes first and last vertex are same,returns false if point is on the line of polygon
if(P.size()==0)
return false;
int j=P.size()-1;
double sum=0;
for(int i=0;i<j;i++)
{
if(onSegment(P[i],p,P[i+1]))
return false;
point a=p,b=P[i],c=P[i+1];
double ux=b.x-a.x,uy=b.y-a.y;
double vx=c.x-a.x,vy=c.y-a.y;
double angle=acos((ux*vx+uy*vy)/sqrt((ux*ux+uy*uy)*(vx*vx+vy*vy)));
if(angle<0)
sum=sum-angle;
else
sum=sum+angle;
}
return (fabs(sum-2*pi)<EPS||fabs(sum+2*pi)<EPS);
}

double polar_angle_of_p2_from_reference_p1(point p1,point p2)
{
double delta_x = p2.x - p1.x;
double delta_y = p2.y - p1.y;
if(theta_degree<0)
theta_degree=theta_degree+360;
return theta_degree;
}

int main()
{
int i,n;
point p,p1;
while(cin>>n&&n)
{
vector<point>v;
for(i=0;i<n;i++)
{
cin>>p.x>>p.y;
v.push_back(p);
}
for(i=0;i<n;i++)
{
if(i==0)
p1=v[i];
else
{
if(p1.y>p.y)
p1=p;
else if(fabs(p1.y-p.y)<EPS&&p1.x>p.x)
p1=p;
}
}
for(i=0;i<n;i++)
{
v[i].angle=polar_angle_of_p2_from_reference_p1(p1,v[i]);
p=v[i];
}
sort(v.begin(),v.end(),compare);
v.push_back(v[0]);
cin>>p.x>>p.y;
if(inPolygon(p,v))
cout<<"T\n";
else
cout<<"F\n";
}
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 634 - Polygon

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!