本文共 4122 字，大约阅读时间需要 13 分钟。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--) 14 #define re(i,l,r) for(int i=(l);i<=(r);i++) 15 #define Clear(a,b) memset(a,b,sizeof(a)) 16 #define inout(x) printf("%d",(x)) 17 #define douin(x) scanf("%lf",&x) 18 #define strin(x) scanf("%s",(x)) 19 #define LLin(x) scanf("%lld",&x) 20 #define op operator 21 #define CSC main 22 typedef unsigned long long ULL; 23 typedef const int cint; 24 typedef long long LL; 25 using namespace std; 26 void inin(int &ret) 27 { 28 ret=0;int f=0;char ch=getchar(); 29 while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=getchar();} 30 while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar(); 31 ret=f?-ret:ret; 32 } 33 const double eps=1e-8; 34 const double pi=acos(-1); 35 const double inf=2147483647; 36 double f(const long double &a){ return a*a;} 37 inline int dcmp(const long double &a){ return abs(a) <0?-1:1;} 38 struct xl 39 { 40 double x,y; 41 xl(double x=0.,double y=0.):x(x),y(y){} 42 void in(){douin(x),douin(y);} 43 bool op == (const xl &rhs)const { return !dcmp(x-rhs.x)&&!dcmp(y-rhs.y);} 44 bool op < (const xl &rhs)const { return !dcmp(x-rhs.x)?y 0&&t2>0)return v2.len(); 87 if(t1<0&&t2<0)return v1.len(); 88 return distoline(a,l); 89 } 90 xl getpoty(const xl &a,const LINE &l) 91 { 92 xl v=l.v-l.u; 93 return l.u+v*D_(a-l.u,v)/D_(v,v); 94 } 95 bool pdxjseg(const LINE &a,const LINE &b) 96 { 97 xl u1=a.u-b.u,u2=a.v-b.u,u=a.v-a.u; 98 xl v1=b.u-a.u,v2=b.v-a.u,v=b.v-b.u; 99 int t1=dcmp(X_(u1,v)),t2=dcmp(X_(u2,v));100 int t3=dcmp(X_(v1,u)),t4=dcmp(X_(v2,v));101 return t1*t2<=0&&t3*t4<=0;102 }103 bool onseg(const xl &a,const LINE &l)104 {105 return !dcmp(D_(a-l.u,a-l.v))&&dcmp(X_(a-l.u,a-l.v))<=0;106 }107 struct cir108 {109 xl c;double r;110 cir(xl c=xl(0.,0.),double r=0):c(c),r(r){}111 bool op < (const cir &rhs)const { return c==rhs.c?r 0)return 0;118 if(!dcmp(d-c.r))return ans1=getpoty(c.c,l),1;119 xl temp=getpoty(c.c,l);120 xl v=c.c-temp;swap(v.x,v.y);121 double len=sqrt(f(c.r)-f(v.len()));122 v=v*len/v.len();123 ans1=temp+v,ans2=temp-v;124 return 2;125 }126 int getjd(const cir &a,const cir &b,xl &ans1,xl &ans2)127 {128 double d=(b.c-a.c).len();129 if(!dcmp(d))if(!dcmp(b.r-a.r))return inf;else return 0;else ;130 if(dcmp(a.r+b.r-d)<0||dcmp(fabs(a.r-b.r)-d)>0)return 0;131 double rad=(b.c-a.c).angle();132 double da=acos((f(a.r)+f(d)-f(b.r))/(2*a.r*d));133 ans1=a.point(rad-da);134 xl ans3=a.point(rad+da);135 if(ans1==ans3)return 1;136 ans2=ans3;return 2;137 }138 int gettangents(cir &A,cir &B,LINE *ans)139 {140 if(A.c==B.c)if(!dcmp(A.r-B.r))return inf;141 else return 0;else ;142 if(A.r 0&&d1<=0&&d2>0)sum++;200 if(k<0&&d2<=0&&d1>0)sum--;201 }202 if(sum!=0)return 1;203 return 0;204 }205 void hull(pol &p,pol &ch)206 {207 int n=p.n,m=0;208 p.Sort();209 re(i,0,n-1)210 {211 while(m>1&&dcmp(X_(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<0)m--;212 ch[m++]=p[i];213 }214 int k=m;215 rre(i,n-1,0)216 {217 while(m>k&&dcmp(X_(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<0)m--;218 ch[m++]=p[i];219 }220 if(n>1)m--;221 ch.n=m;222 }223 double lenofpol(pol &p)224 {225 double ret=0;226 re(i,0,p.n-1)ret+=(p[(i+1)%p.n]-p[i]).len();227 return ret;228 }229 double areaofpol(pol &p)230 {231 double ret=0;int n=p.n;232 re(i,1,n-2)ret+=X_(p[i]-p[0],p[i+1]-p[0]);233 return ret/2;234 }235 double diameterofhull(pol &p)236 {237 int n=p.n;double ret=0.;238 if(n<=1)return 0.;239 if(n==2)return dis2(p[0],p[1]);240 int r=1;241 re(l,0,n-1)while(1)242 {243 double d=X_(p[l+1]-p[l],p[r+1]-p[r]);244 if(dcmp(d)<=0)245 {246 ret=max(ret,dis2(p[l],p[r]));247 if(!dcmp(d))ret=max(ret,dis2(p[l],p[r+1]));248 break;249 }250 r++,r%=n;251 }252 return ret;253 }254 bool onleft(const xl &a,const LINE &l){ return X_(l.v-l.u,a-l.u)>0;}255 bool halfplanej(LINE *l,int n,pol &ch)256 {257 re(i,0,n-1)l[i].js();258 sort(l,l+n);259 int ll=0,rr=0;260 xl p[n];261 LINE q[n];q[0]=l[0];262 re(i,1,n-1)263 {264 while(ll
转载于:https://www.cnblogs.com/HugeGun/p/5254164.html