只因算寄何板子
KING_OF_TURTLE · · 个人记录
#include<bits/stdc++.h>
const int N=100005;
using namespace std;
typedef long double ld;
const ld eps=1e-10;
const ld inf=1e18;
int dcmp(ld x){return x<-eps?-1:(x>eps?1:0);}
ld sqr(ld x){return x*x;}
struct Point{
ld x,y;
Point(ld _x=0,ld _y=0):x(_x),y(_y){}
bool operator<(const Point &rhs)const{
return x==rhs.x?y<rhs.y:x<rhs.x;
}
void read(){scanf("%Lf%Lf",&x,&y);}
void print(){printf("%.10Lf %.10Lf\n",x,y);}
};
typedef Point Vector;
bool cmp_y(const Point &A,const Point &B){return A.y==B.y?A.x<B.x:A.y<B.y;}
Vector operator +(const Vector A,const Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator -(const Vector A,const Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator *(const Vector A,const ld L){return Vector(A.x*L,A.y*L);}
Vector normal(const Vector A){return Vector(-A.y,A.x);}
bool operator ==(const Point A,const Point B){return !dcmp(A.x-B.x)&&!dcmp(A.y-B.y);}
ld len(const Vector A){return sqrtl(A.x*A.x+A.y*A.y);}
ld dot(const Vector A,const Vector B){return A.x*B.x+A.y*B.y;}
ld cross(const Vector A,const Vector B){return A.x*B.y-A.y*B.x;}
ld angle(const Vector A,const Vector B){return acos(dot(A,B)/len(B)/len(A));}
Point turn(const Point A,const ld theta){return Point(A.x*cos(theta)+A.y*sin(theta),-A.x*sin(theta)+A.y*cos(theta));}
Point turn(const Point A,const Point B,const ld theta){return turn(A-B,theta)+B;}
bool on_PL(const Point P,const Point A,const Point B){return !dcmp(cross(P-A,B-A))&&dcmp(dot(P-A,P-B))<=0;}
ld dis_PL(const Point P,const Point A,const Point B)
{
if(A==B)return len(P-A);
if(dcmp(dot(B-A,B-P))<0)return len(P-B);
if(dcmp(dot(A-B,A-P))<0)return len(P-A);
return fabs(cross(A-P,A-B)/len(A-B));
}
int side(const Point A,const Point B,const Point P){return dcmp(cross(P-A,B-A))>0;}
bool on_PLL(const Point P,const Point A,const Point B){return !dcmp(cross(P-A,B-A));}
Point footPoint(const Point P,const Point A,const Point B)
{ld lena=dot(P-A,B-A)/len(B-A),lenb=-1.0*dot(P-B,B-A)/len(B-A);return A+(B-A)*(lena/(lena+lenb));}
Point Turnover(const Point P,const Point A,const Point B){return footPoint(P,A,B)*2-P;}
Point intersec(const Point A,const Point B,const Point C,const Point D){return A+(B-A)*(cross(D-C,A-C)/cross(B-A,D-C));}
struct Line{
Point A,B;ld k;
Line(Point _A=Point(0,0),Point _B=Point(0,0)){A=_A;B=_B;k=atan2((A.y-B.y),(A.x-B.x));}
bool operator<(const Line rhs)const{
return dcmp(k-rhs.k)?dcmp(k-rhs.k)<0:side(A,B,rhs.A);
}
};
Point intersec(const Line L1,const Line L2){return intersec(L1.A,L1.B,L2.A,L2.B);}
ld dis_PLL(const Point P,const Line L){return len(footPoint(P,L.A,L.B)-P);}
int side(const Line L,const Point P){return side(L.A,L.B,P);}
bool Line_Segment(const Point A,const Point B,const Point C,const Point D){return on_PLL(intersec(A,B,C,D),C,D);}
bool Segment_Segment(const Point A,const Point B,const Point C,const Point D)
{return dcmp(cross(B-A,C-A))*dcmp(cross(B-A,D-A))<0&&dcmp(cross(A-D,C-D))*dcmp(cross(B-D,C-D))<0;}
bool parallel(const Line P,const Line Q){return !dcmp(cross(P.B-P.A,Q.B-Q.A));}
struct Polygen{
vector<Point> a;int n;
void read_n(){scanf("%d",&n);a.resize(n);}
void read_a(){for(int i=0;i<n;++i)a[i].read();}
void insert(Point p){a.push_back(p);++n;}
ld area()
{
ld res=0;
for(int i=0;i<n;++i)
res+=cross(a[i],a[(i+1)%n]);
return fabs(res)/2;
}
ld Perimeter()
{
ld res=0;
for(int i=0;i<n;++i)
res+=len(a[i]-a[(i+1)%n]);
return res;
}
bool Point_in(const Point A)
{
int cnt=0;
for(int i=0;i<n;++i)
{
Point S=a[i],T=a[(i+1)%n];
if(on_PL(A,S,T))return 1;
if(A.y>=min(S.y,T.y)&&A.y<max(S.y,T.y))
cnt+=(dcmp(S.x+(T.x-S.x)*(A.y-S.y)/(T.y-S.y)-A.x)>0);
}
return cnt&1;
}
bool Point_in_fast(const Point P)
{
if(side(a[0],a[1],P)||side(a[n-1],a[0],P))return 0;
if(on_PL(P,a[0],a[1])||on_PL(P,a[n-1],a[1]))return 1;
int l=2,r=n-1,ans=2;
while(l<=r)
{
int mid=((l+r)>>1);
if(side(a[0],P,a[mid]))ans=mid,l=mid+1;
else r=mid-1;
}
if(side(a[ans],a[(ans+1)%n],P))return 0;
if(on_PL(P,a[ans],a[(ans+1)%n]))return 1;
return 1;
}
void to_convexhull()
{
sort(a.begin(),a.end(),cmp_y);
int t=0;vector<Point> b;
for(int i=0;i<n;++i)
{
while(t>1&&dcmp(cross(b[t-1]-b[t-2],a[i]-b[t-2]))<=0)--t,b.pop_back();
b.push_back(a[i]);++t;
}
int tmp=t;
for(int i=n-1;i>=0;--i)
{
while(t>tmp&&dcmp(cross(b[t-1]-b[t-2],a[i]-b[t-2]))<=0)--t,b.pop_back();
b.push_back(a[i]);++t;
}
--t;n=t;swap(a,b);
}
ld diameter()
{
if(n==2)return len(a[1]-a[0]);ld ans=len(a[1]-a[0]);
for(int i=0,j=2;i<n;++i)
{
while(dcmp(cross(a[(i+1)%n]-a[i],a[j]-a[i])-cross(a[(i+1)%n]-a[i],a[(j+1)%n]-a[i]))<0)j=(j+1)%n;
ans=max(ans,len(a[(i+1)%n]-a[i]));ans=max(ans,max(len(a[(i+1)%n]-a[j]),len(a[i]-a[j])));
}
return ans;
}
ld max_triangle()
{
if(n==2)return 0;ld ans=0;
for(int i=0,j=2;i<n;++i)
{
while(dcmp(cross(a[(i+1)%n]-a[i],a[j]-a[i])-cross(a[(i+1)%n]-a[i],a[(j+1)%n]-a[i]))<0)j=(j+1)%n;
ans=max(ans,cross(a[(i+1)%n]-a[i],a[j]-a[i])/2);
}
return ans;
}
Polygen(){a.clear();n=0;}
void print(){if(n<=2)return printf("0"),void();printf("%d\n",n);for(int i=0;i<n;++i)a[i].print();}
};
Line Q[N],L[N];Vector V1[N],V2[N];
Polygen Minkowski(const Polygen A,const Polygen B)
{
Polygen res;
for(int i=0;i<A.n;++i)V1[i]=A.a[(i+1)%A.n]-A.a[i];
for(int i=0;i<B.n;++i)V2[i]=B.a[(i+1)%B.n]-B.a[i];
int l=0,r=0;res.insert(V1[0]+V2[0]);
while(l<A.n&&r<B.n)res.insert(res.a.back()+(dcmp(cross(V1[l],V2[r]))>0?V1[l++]:V2[r++]));
while(l<A.n)res.insert(res.a.back()+V1[l++]);while(r<B.n)res.insert(res.a.back()+V2[r++]);
return res;
}
Polygen halfcut(Line *L,int n)
{
sort(L+1,L+n+1);int m=n;n=0;
for(int i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[n].k))L[++n]=L[i];
int st=1,ed=0;
for(int i=1;i<=n;++i)
{
while(st<ed&&side(L[i],intersec(Q[ed],Q[ed-1])))--ed;
while(st<ed&&side(L[i],intersec(Q[st],Q[st+1])))++st;
if(st<=ed&&!dcmp(L[i].k+Q[ed].k)&&side(L[i],Q[ed].A))return Polygen();
Q[++ed]=L[i];
}
while(st<ed&&side(Q[st],intersec(Q[ed],Q[ed-1])))--ed;
while(st<ed&&side(Q[ed],intersec(Q[st],Q[st+1])))++st;
Polygen res;
for(int i=st;i<=ed;++i)res.insert(intersec(Q[i],Q[i<ed?i+1:st]));
return res;
}
const ld pi=acos(-1);
struct Circle{
Point o;ld r;
Circle(Point _o=Point(0,0),ld _r=0):o(_o),r(_r){}
ld area(){return r*r*pi;}
ld Perimeter(){return 2*pi*r;}
bool Point_in(const Point A){return dcmp(len(A-o)-r)<=0;}
};
Circle threePoint(const Point A,const Point B,const Point C)
{
Point P1=(A+B)*0.5,P2=(A+C)*0.5;
Point o=intersec(P1,P1+normal(B-A),P2,P2+normal(C-A));
return Circle(o,len(o-A));
}
Circle minCircle(Point *P,int n)
{
mt19937 rnd(time(0));shuffle(P+1,P+n+1,rnd);
Circle res=Circle(P[1],0);
for(int i=2;i<=n;++i)if(!res.Point_in(P[i]))
{
res=Circle(P[i],0);
for(int j=1;j<i;++j)if(!res.Point_in(P[j]))
{
res.o=(P[i]+P[j])*0.5;res.r=len(P[j]-res.o);
for(int k=1;k<j;++k)if(!res.Point_in(P[k]))res=threePoint(P[i],P[j],P[k]);
}
}
return res;
}
bool Segment_Circle(const Point A,const Point B,const Circle C){return dcmp(dis_PL(C.o,A,B)-C.r)<=0;}
bool Line_Circle(const Line L,const Circle C){return dcmp(dis_PLL(C.o,L)-C.r)<=0;}
pair<Point,Point> Line_Circle(const Point A,const Point B,const Circle C)
{
Point P=footPoint(C.o,A,B);
ld tmp=sqrt((sqr(C.r)-len(P-C.o))/(sqr(A.x-B.x)+sqr(A.y-B.y)));if(!dcmp(tmp))return make_pair(P,P);
return make_pair(P+Vector(tmp*(A.x-B.x),tmp*(A.y-B.y)),P-Vector(tmp*(A.x-B.x),tmp*(A.y-B.y)));
}
int Circle_Circle(const Circle C1,const Circle C2)
{
if(dcmp(len(C1.o-C2.o)-C1.r-C2.r)>0)return 0;//相离
if(!dcmp(len(C1.o-C2.o)-C1.r-C2.r))return 1;//相切
if(dcmp(len(C1.o-C2.o)-fabs(C1.r-C2.r))<=0)return 2;//包含或内切
return -1;//相交
}
pair<Point,Point> Circle_intersec(const Circle C1,const Circle C2)
{
ld tmp=len(C1.o-C2.o);
ld a1=acos((sqr(C1.r)+sqr(tmp)-sqr(C2.r))/2/C1.r/tmp);
ld a2=acos((sqr(C2.r)+sqr(tmp)-sqr(C1.r))/2/C2.r/tmp);
Point P=turn(C2.o,C1.o,a1),Q=turn(C1.o,C2.o,-a2);
Point res1=intersec(P,C1.o,Q,C2.o);
Point res2=Turnover(res1,C1.o,C2.o);
return make_pair(res1,res2);
}
struct Dynamic_convexhull{
set<Point> s;int type;
bool Point_in(const Point P)
{
auto p=s.lower_bound(Point(P.x,-inf));
if(p==s.end())return 0;
if(!dcmp(p->x-P.x))return dcmp(P.y-(p->y))*type<=0;
if(p==s.begin())return 0;return dcmp(cross(P-(*prev(p)),(*p)-(*prev(p))))*type>=0;
}
typedef set<Point>::iterator sit;
bool check(sit it)
{
auto j=it,k=it;
if(j==s.begin())return 0;--j;if(++k==s.end())return 0;
return dcmp(cross(*it-*j,*k-*j))*type>=0;
}
void insert(const Point P)
{
if(Point_in(P))return;
auto p=s.lower_bound(Point(P.x,-inf));
if(p!=s.end()&&!dcmp(P.x-p->x))s.erase(p);
p=s.insert(P).first;auto nw=p;
if(p!=s.begin()){--p;while(check(p)){auto tmp=p--;s.erase(tmp);}}
if((p=++nw)!=s.end())while(check(p)){auto tmp=p++;s.erase(tmp);}
}
}up,down;