634 - Polygon

[anjanpstu]

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:
         return Touching;
         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]

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]

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;
    double theta_radians;
    theta_radians = atan2(delta_y, delta_x);
    double theta_degree=theta_radians* 180 / pi;
    //return theta_radians;
    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]

Try solving it without using floating point.