黑书上的基本函数+线段截多边形,求内核
#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)//瑙e喅绮惧害鐨勫垽鏂皬浜?
{
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;
}
评论