qus的博客

黑书上的基本函数+线段截多边形，求内核

#include<iostream>
#include<math.h>
#define MAXL 55
#define dps 1e-5
using namespace std;
struct point
{
 double x,y;
};
struct node
{
 int n;
 point po[MAXL];
};
int dblcmp(double d)//瑙ｅ喅绮惧害鐨勫垽鏂�灏忎�?
{
 if(fabs(d)<dps) return 0;
 return (d>0)?1:-1;
}
double mymin(double a,double b)
{return a<b?a:b;}
double mymax(double a,double b)
{return a>b?a:b;}
double det(double x1,double y1,double x2,double y2)//姹備袱涓�鍚戦噺鍙夌�?
{
 return x1*y2-x2*y1;
}
double cross(point a,point b,point c)//姹?涓�鐐圭殑鍙夌�?
{
 return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}
int xycmp(double p,double mini,double maxi)
{
 return dblcmp(p-mini)*dblcmp(p-maxi);
}
int betweencmp(point a,point b,point c) //宸茬粡鐭ラ亾a鍦╞c鐩寸嚎涓?,杩斿洖鍊? 涓嶅湪閲岄潰锛? c鍦ㄧ��鐐筧鎴栬?卋 锛岋紞1 c鍦ㄧ��鐐筧 b涔嬮棿
{
 if(fabs(b.x-c.x)>fabs(b.y-c.y)) return xycmp(a.x,mymin(b.x,c.x),mymax(b.x,c.x));
 else return xycmp(a.y,mymin(b.y,c.y),mymax(b.y,c.y));

}
int segcross(point a,point b,point c,point d,point &p)//p鐢ㄤ簬寮曠敤杩斿洖鏁?
{
 double s1,s2,s3,s4;
 int d1,d2,d3,d4;
 d1=dblcmp(s1=cross(a,b,c));
 d2=dblcmp(s2=cross(a,b,d));
 d3=dblcmp(s3=cross(c,d,a));
 d4=dblcmp(s4=cross(c,d,b));

 //鍒ゆ柇瑙勮寖鐩镐氦
 if((d1^d2)==-2&&(d3^d4)==-2)
 {
  p.x=(c.x*s2-d.x*s1)/(s2-s1);
  p.y=(c.y*s2-d.y*s1)/(s2-s1);
  return 1;
 }
 //鍒ゆ柇闈炶�勮寖鐩镐�?
 /*if(d1==0&&betweencmp(c,a,b)<=0) {p=c;return 2;}
 if(d2==0&&betweencmp(d,a,b)<=0) {p=d;return 2;}
 if(d3==0&&betweencmp(a,c,d)<=0) {p=a;return 2;}
 if(d4==0&&betweencmp(b,c,d)<=0) {p=d;return 2;}*/

 return 0;
}
node cut(point a,point b,node now)
{
 node re;re.n=0;
 int pre,temp,i;
 //寤堕暱绾挎�靛埌鐩寸�?
 double dx=a.x-b.x;
 double dy=a.y-b.y;
 a.x+=dx*1e10; b.x-=dx*1e10;
 a.y+=dy*1e10; b.y-=dy*1e10;
 point return_point;
 pre=dblcmp(cross(a,b,now.po[now.n-1]));
 for(i=0;i<now.n;i++)
 {
  temp=dblcmp(cross(a,b,now.po[i]));
  if(pre==1&&temp==-1 || pre==-1&&temp==1 )
  {
   if(i==0 )segcross(a,b,now.po[i],now.po[now.n-1],return_point);
   else segcross(a,b,now.po[i],now.po[i-1],return_point);
   re.po[re.n]=return_point;
   re.n++;
  }
  if(temp>=0) re.po[re.n++]=now.po[i];
  pre=temp;
 }
 return re;
}
int main()
{
 //freopen("in.txt","r",stdin);
 int i,t1,t2;
 node in,now;
 while(scanf("%d",&in.n))
 {
  if(in.n==0) break;
  for(i=0;i<in.n;i++)
  {
   scanf("%d%d",&t1,&t2);
   in.po[i].x=t1;in.po[i].y=t2;
  }
  now=in;
  for(i=0;i<in.n;i++)
  {
   if(i==in.n-1) now=cut(in.po[i],in.po[0],now);
   else now=cut(in.po[i],in.po[i+1],now);
   if(now.n==0) break;
  }
  if(i==in.n) printf("1\n");
  else printf("0\n");
 }
 return 0;
}