1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
|
double A,B,C; A=y2-y1; B=x1-x2; C=x2*y1-x1*y2;
double d=fabs(A*x0+B*y0+C)/sqrt(A*A+B*B);
double x,y; x=(B*B*x0-A*B*y0-A*C)/(A*A+B*B); y=(-A*B*x0+A*A*y0-B*C)/(A*A+B*B);
double k,_x,_y; k=-2*(A*x0+B*y0+C)/(A*A+B*B); _x=x0+k*A; _y=y0+k*B;
int t1,t2,t3; t1=gcd(abs(x1-x2),abs(y1-y2)); t2=gcd(abs(x3-x2),abs(y3-y2)); t3=gcd(abs(x1-x3),abs(y1-y3)); int num; num=abs((x2-x1)*(y3-y2)-(x3-x2)*(y2-y1))/2; num-=(t1+t2+t3)/2-1;
struct point{ double x,y; point(double _x=0,double _y=0){ x=_x,y=_y; } point operator+ (const point& a) const{ return point(x+a.x,y+a.y); } point operator- (const point& a) const{ return point(x-a.x,y-a.y); } point operator* (double a) const{ return point(x*a,y*a); } }; struct line{ point s,e; line(point a,point b){ s=a,e=b; } line(){} }; int dcmp(double x){ if(x>eps) return 1; return x<-eps?-1:0; } double getdis(point a, point b){ double xx=a.x-b.x,yy=a.y-b.y; return sqrt(xx*xx+yy*yy); } double multi(point a,point b,point c){ double xa,ya,xb,yb; xa=b.x-a.x; ya=b.y-a.y; xb=c.x-b.x; yb=c.y-b.y; return xa*xb+ya*yb; } double cross(point a,point b,point c){ double xa,ya,xb,yb; xa=b.x-a.x; ya=b.y-a.y; xb=c.x-a.x; yb=c.y-a.y; return xa*yb-xb*ya; } int judgec(line a,line b){ if (max(a.s.x,a.e.x)>=min(b.s.x,b.e.x) && max(a.s.y,a.e.y)>=min(b.s.y,b.e.y) && max(b.s.x,b.e.x)>=min(a.s.x,a.e.x) && max(b.s.y,b.e.y)>=min(a.s.y,a.e.y) && cross(a.s,b.s,b.e)*cross(a.e,b.s,b.e)<=0 && cross(b.s,a.s,a.e)*cross(b.e,a.s,a.e)<=0 ) return 1; else return 0; } point getpoi(point a,point b,point c,point d){ double u=cross(a,b,c),v=cross(b,a,d); return point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v)); } double parea(point p[],int n){ if(n<3) return 0; double ans=0; p[n]=p[0]; rep(i,0,n) ans+=p[i].x*p[i+1].y-p[i+1].x*p[i].y; return ans/2; }
double CPIA(point a[],point b[],int n1,int n2){ if(n2<3) return 0; point p[15],t[15]; a[n1]=a[0]; b[n2]=b[0]; memcpy(p,b,sizeof(point)*(n2+1)); rep(i,0,n1){ int f1=dcmp(cross(a[i],a[i+1],p[0])),tn=0; rep(j,0,n2){ if(f1>=0) t[tn++]=p[j]; int f2=dcmp(cross(a[i],a[i+1],p[j+1])); if((f1^f2)==-2) t[tn++]=getpoi(a[i],a[i+1],p[j],p[j+1]); f1=f2; } memcpy(p,t,sizeof(point)*tn); n2=tn; p[n2]=p[0]; } return parea(p,n2); } double SPIA(point a[],point b[],int n1,int n2){ point t1[5],t2[5]; a[n1]=t1[0]=a[0]; b[n2]=t2[0]=b[0]; double res=0; rep(i,2,n1){ t1[1]=a[i-1]; t1[2]=a[i]; int f1=dcmp(cross(t1[0],t1[1],t1[2])); if(f1<0) swap(t1[1],t1[2]); rep(j,2,n2){ t2[1]=b[j-1]; t2[2]=b[j]; int f2=dcmp(cross(t2[0],t2[1],t2[2])); if(f2<0) swap(t2[1],t2[2]); res+=CPIA(t1,t2,3,3)*f1*f2; } } return fabs(res); } double gx, gy; void find_gra(){ double area=0,tmp; rep(i,1,n-1){ tmp=(p[i].x-p[0].x)*(p[i+1].y-p[0].y)-(p[i+1].x-p[0].x)*(p[i].y-p[0].y); area+=tmp; gx+=(p[0].x+p[i].x+p[i+1].x)*tmp; gy+=(p[0].y+p[i].y+p[i+1].y)*tmp; } gx=gx/3/area, gy=gy/3/area; }
|