1081a.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

const double EPS=1e-9;
const double INF=1e10;
const double PI=acos(-1.);
const int MAXN=1000;

struct Point {double x,y;};

inline double max(double x,double y)
{
  return (x>y+EPS)?x:y;
}

inline double min(double x,double y)
{
  return (x+EPS<y)?x:y;
}

bool same(Point &a,Point &b)
{
  return(fabs(a.x-b.x)<EPS && fabs(a.y-b.y)<EPS);
}

//distance from a tob;
double dis(Point &a,Point &b)
{
  double dx=a.x-b.x,dy=a.y-b.y;
  return sqrt(dx*dx+dy*dy);
}

//cross-product
double cross(Point &a,Point &b,Point &c)
{
  return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
}

//line p-q:ax+by+c=0 compute a,b,c
void linec(Point &p,Point &q,double &a,double &b,double &c)
{
  a=p.y-q.y,b=q.x-p.x,c=p.y*(p.x-q.x)-p.x*(p.y-q.y);
}

//intersect of line p1-p2 and line q1-q2
int line_int(Point &p1,Point &p2,Point &q1,Point &q2,Point &p)
{
  double a1,b1,c1,a2,b2,c2;
  double d1,d2,d;

  linec(p1,p2,a1,b1,c1);
  linec(q1,q2,a2,b2,c2);
  d=a1*b2-a2*b1;
  d1=-c1*b2+b1*c2,d2=-a1*c2+a2*c1;
  if(fabs(d)<EPS) {
    if(fabs(d1)<EPS && fabs(d2)<EPS) return 2;
    return 0;
  }
  else {
    p.x=d1/d,p.y=d2/d;
    return 1;
  }
}

//check intersect of segment p1-p2 and segment q1-q2
bool seg_int_check(Point &p1,Point &p2,Point &q1,Point &q2)
{
  if(max(p1.x,p2.x)<min(q1.x,q2.x)-EPS || 
     min(p1.x,p2.x)>max(q1.x,q2.x)+EPS ||
     max(p1.y,p2.y)<min(q1.y,q2.y)-EPS ||
     min(p1.y,p2.y)>max(q1.y,q2.y)+EPS) return 0;
  if(cross(p1,p2,q1)*cross(p1,p2,q2)>EPS ||
     cross(q1,q2,p1)*cross(q1,q2,p2)>EPS) return 0;
  return 1;
}

//intersect of segment p1-p2 and segment q1-q2
int seg_int(Point &p1,Point &p2,Point &q1,Point &q2,Point &p)
{
  if(!seg_int_check(p1,p2,q1,q2)) return 0;
  return line_int(p1,p2,q1,q2,p);
}

//angle from AB to AC
double angle(Point &a,Point &b,Point &c)
{
  double l1,l2,l3,ret;

  l1=dis(a,b);l2=dis(a,c);l3=dis(b,c);
  ret=acos((l1*l1+l2*l2-l3*l3)/l1/l2*.5);
  if(cross(a,b,c)>-EPS) return ret;
  return -ret;
}

//check whether q on line p1-p2
bool check_online(Point &q,Point &p1,Point &p2)
{
  return(fabs(cross(q,p1,p2))<EPS);
}

//check whether q on segment p1-p2
bool check_onseg(Point &q,Point &p1,Point &p2)
{
  if(!check_online(q,p1,p2)) return false;
  if(fabs(p1.x-p2.x)<EPS) return ((q.y-p1.y)*(q.y-p2.y)<EPS);
  return ((q.x-p1.x)*(q.x-p2.x)<EPS);
}

//check whether q in polygon p
//-1:out 0:on the boundary 1:in
int p_in_polygon(Point &q,int n,Point p[])
{
  int i;
  double tota=0.;

  for(i=0;i<n;i++) {
    if(check_onseg(q,p[i],p[(i+1)%n])) return 0;
    tota+=angle(q,p[i],p[(i+1)%n]);
  }
  if(fabs(tota)>3.) return 1;
  return -1;    
}

bool samesidel(Point &a,Point &b,Point &l1,Point &l2)
{
	if(cross(l1,l2,a)*cross(l1,l2,b)>-EPS)return true;
	return false;
}
//another vision by Carp,faster 
int in_polygon(Point p,Point v[],int n)
{
  int i,count=0;
  Point r;
  v[n]=v[0],v[n+1]=v[1],v[n+2]=v[2];
  r.x=INF+1.,r.y=p.y+1.;
  for(i=0;i<n;i++){
    if (check_onseg(p,v[i],v[i+1])) return 0;
	if (seg_int_check(r,p,v[i],v[i+1]) ||
		check_online(v[i+1],p,r) && ( !check_online(v[i+2],p,r) && !samesidel(v[i],v[i+2],p,r)
		|| check_online(v[i+2],p,r) && !samesidel(v[i],v[i+3],p,r)))count++;

  }
  if (count%2==1) return 1;
  return -1;
}

//return the convex of set of points
int sort_y(Point *p1,Point *p2)
{
  if(p1->y > p2->y+EPS) return -1;
  if(p1->y+EPS < p2->y) return 1;
  if(p1->x+EPS < p2->x) return -1;
  return 1;
}
void convex(int n,Point *a,int &m,Point *p)
{
  int ls,rs;  
  Point l[MAXN],r[MAXN];
  int i,j;

  m=n;
  memcpy(p,a,sizeof(Point)*n);
  if(m<3) return;  
  qsort(p,m,sizeof(Point),(int(*)(const void *,const void *))sort_y);

  /*if same points exist in the given set:
  j=1;
  for(i=1;i<m;i++) if(!same(p[i],p[i-1])) p[j++]=p[i];
  m=j;
  if(m<3) return;
  */

  l[0]=r[0]=p[0];
  l[1]=r[1]=p[1];
  ls=rs=2;
  for(i=2;i<m;i++) {
    while(ls>1 && cross(l[ls-2],l[ls-1],p[i])>-EPS) ls--;
    while(rs>1 && cross(r[rs-2],r[rs-1],p[i])<EPS) rs--;
    /*find all the points on the convex:
    while(ls>1 && cross(l[ls-2],l[ls-1],p[i])>EPS) ls--;
    while(rs>1 && cross(r[rs-2],r[rs-1],p[i])<-EPS) rs--;
    */
    l[ls++]=r[rs++]=p[i];
  }

  m=0;
  for(i=0;i<rs;i++) p[m++]=r[i];
  for(i=ls-2;i>0;i--) p[m++]=l[i];
}

/*diameter of convex polygon
  given a convex, return the distance of the farthest pair*/
double convex_diameter(int n,Point *p,int &p1,int &p2)
{
  Point q[MAXN];
  int i,j;
  double a,d;
  double ret=0.;

  if(n==1) return 0.;
  if(n==2) {
    p1=0,p2=1;
    return dis(p[0],p[1]);
  }
  
  for(i=0;i<n;i++) {
    j=(i+1)%n;
    q[i].x=(p[i].x+p[j].x)*.5,q[i].y=(p[i].y+p[j].y)*.5;    
  }
  i=0;
  while(1) {
    j=(i+1)%n;
    while(1) {
      a=angle(q[j],p[i],p[j]);
      if(a+EPS<PI*.5) j=(j+1)%n; else {
	d=dis(p[i],p[j]);
	if(d>ret+EPS) ret=d,p1=i,p2=j;
	break;
      }
    }
    if(i==n-1) break;
    i++;
  }
  return ret;
}


Point a[1000];

int main()
{
  int n,m;
  int i,j,k;
  int T=0;
  while(scanf("%d",&n)!=EOF)
  {
	  if(n==0)break;
	  T++;
	  scanf("%d",&m);
	  for(i=0;i<n;i++)
	  {
		  scanf("%lf%lf",&a[i].x,&a[i].y);
	  }
	  if(T!=1)printf("\n");
	  printf("Problem %d:\n",T);

	  for(i=0;i<m;i++)
	  {
		  Point tmp;
		  scanf("%lf%lf",&tmp.x,&tmp.y);
		  if(in_polygon(tmp,a,n)==-1)
			  printf("Outside\n");
		  else
			  printf("Within\n");
	  }
  }


}