首页 > 其他分享 >计算几何

计算几何

时间：2022-08-26 21:46:28浏览次数：48  
标签：node tmp return int top 计算 几何 inc

计算几何基础

const double eps=1e-8
//向量的基本运算 
struct node{
	double x,y;
	node(){}	
	node(double xx,double yy){x=xx,y=yy;}
}; 
node operator+(node a,node b){return node(a.x + b.x, a.y + b.y);}
node operator-(node a,node b){return node(a.x - b.x, a.y - b.y);}
node operator*(node a,double t){return node(a.x * t, a.y * t)} //数乘
node operator/(node a,double t){return node(a.x / t, a.y / t)}
double dot(node a,node b){ //点乘 
	return a.x * b.x + a.y * b.y; 
}
double cross(node a,node b){ //叉乘
	return a.x * b.y - a.y * b.x; 	
}
double dis(node a,node b){//两点间距离
	return sqrt(dot(a - b, a - b));
}
//直线与线段的运算 
struct line{
	node s, t;
	//s为直线上一点，t为直线的方向向量 
	//当s+t为终点时也可以表示线段 
};
bool line_cross(line a,line b){//线段相交
	node as = a.s, at = a.s + a.t;
	node bs = b.s, bt = b.s + b.t;
	return (cross(as - bs, as - bt) * cross(at - bs, at - bt) < eps) 
}
node cross_node(line a,line b){//直线交点 
	node p = a.s - b.s;
	double t = cross(b.t, p) / cross(a.t b.t);
	return p + t * a.t
}

凸包

#include<bits/stdc++.h>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
const int MAXN=100005;
using namespace std;
struct node{
	double x,y;
}v[MAXN];
bool cmp(node x,node y){
	return x.x!=y.x?x.x<y.x:x.y<y.y;
}
bool getk(int a,int b,int c,int d){
	return (v[a].y-v[b].y)*(v[c].x-v[d].x)<(v[c].y-v[d].y)*(v[a].x-v[b].x);
}
double dis(int a,int b){
	return sqrt((v[a].x-v[b].x)*(v[a].x-v[b].x)+(v[a].y-v[b].y)*(v[a].y-v[b].y));
}
double ans;
int n,z[MAXN],top;
int main(){
	scanf("%d",&n);
	inc(i,1,n) scanf("%lf%lf",&v[i].x,&v[i].y);
	sort(v+1,v+1+n,cmp);
	z[1]=1,top=1;
	inc(i,2,n){
		while(top>=2&&getk(i,z[top-1],z[top],z[top-1])) top--;
		z[++top]=i;
	}
	inc(i,1,top-1) ans+=dis(z[i],z[i+1]);
	z[1]=n,top=1;
	dec(i,n-1,1){
		while(top>=2&&getk(i,z[top-1],z[top],z[top-1])) top--;
		z[++top]=i;
	}
	dec(i,top,2) ans+=dis(z[i],z[i-1]);
	printf("%.2lf",ans);
}

动态凸包

#include<bits/stdc++.h>
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;i++)
using namespace std;
const int MAXN=505;
const double eps=1e-10;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=x*10+ch-'0',ch=getchar();}
	return f*x;
}
int n,m,cnt;
struct point{
	double x,y;
	point operator+(const point a){return (point){x+a.x,y+a.y};}
	point operator-(const point a){return (point){x-a.x,y-a.y};}
	point operator*(double a){return (point){x*a,y*a};}
	double crs(point a){return x*a.y-y*a.x;}
}p[MAXN];
struct line{
	point s,t;
	double tang(){return atan2(t.y,t.x);}
}L[MAXN];
bool operator<(line x,line y){return x.tang()<y.tang();}
point insert(line l1,line l2){
	point u=l2.s-l1.s;
	double t=u.crs(l2.t)/l1.t.crs(l2.t);
	return l1.s+l1.t*t;
}
bool onleft(point a,line b){return b.t.crs(a-b.s)>eps;}
int half(){
	sort(L+1,L+cnt+1);
	int l=1,r=0,tot=0;
	point P[MAXN];
	line q[MAXN];
	q[++r]=L[1];
	inc(i,2,cnt){
	    while(r>l&&!onleft(P[r-1],L[i])) r--;
	    while(r>l&&!onleft(P[l],L[i])) l++;
	    q[++r]=L[i];
	    if(fabs(q[r].t.crs(q[r-1].t))<eps){
	    	r--;
	    	if(!onleft(P[r-1],L[i])) q[r]=L[i];
		}
		if(l<r) P[r-1]=insert(q[r],q[r-1]);
	}
	while(l<r&&!onleft(P[r-1],q[l])) r--;
	if(l+1>r) return 0;
	P[r]=insert(q[l],q[r]);
	inc(i,l,r) p[++tot]=P[i];
	return tot;
}
double solve(int num){
	double res=0;
	inc(i,1,num) res+=p[i].crs(p[i==num?1:i+1]);
	return res/2.0;
}
point pp[55];
int main(){
	n=read();
	inc(i,1,n){
		m=read();
		inc(j,1,m) pp[j].x=read(),pp[j].y=read();
		L[++cnt]=(line){pp[1],pp[1]-pp[m]};
		inc(j,2,m) L[++cnt]=(line){pp[j],pp[j]-pp[j-1]};
	} 
	int num=half();
	printf("%.3lf",solve(num)); 
}

三维凸包

#include<bits/stdc++.h>
#define re register
#define db double
#define inc(i,j,k) for(re int i=j;i<=k;i++)
using namespace std;
const int N=2005;
const db eps=1e-9;
int n,cnt;
bool vis[N][N];
db ans;
db rd(){return (db)rand()/RAND_MAX*eps;}
struct point{
	db x,y,z;
	point(){}
	point(db xx,db yy,db zz){x=xx,y=yy,z=zz;}
	void shake(){x+=rd(),y+=rd(),z+=rd();}
	double len(){return sqrt(x*x+y*y+z*z);}
	point operator-(point a){return point(x-a.x,y-a.y,z-a.z);}
	point operator*(point a){return point(y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x);}
	db operator&(point a){return x*a.x+y*a.y+z*a.z;}
}p[N];
struct plate{
	int v[3];
	plate(){}
	plate(int v0,int v1,int v2){v[0]=v0,v[1]=v1,v[2]=v2;}
	point normal(){return (p[v[1]]-p[v[0]])*(p[v[2]]-p[v[0]]);}
	db area(){return normal().len()/2.0;}
}P[N],F[N];
bool out(plate a,point b){return ((b-p[a.v[0]])&a.normal())>0;}
void solve(){
	P[++cnt]=plate(1,2,3);
	P[++cnt]=plate(3,2,1);
	inc(i,4,n){
		int tot=0;
		inc(j,1,cnt){
			db tmp;
			if(!(tmp=out(P[j],p[i]))) F[++tot]=P[j];
			inc(k,0,2) vis[P[j].v[k]][P[j].v[(k+1)%3]]=tmp;
		}
		inc(j,1,cnt){
			inc(k,0,2){
				int x=P[j].v[k],y=P[j].v[(k+1)%3];
				if(vis[x][y]&&!vis[y][x]) F[++tot]=plate(x,y,i);
			}
		}
		inc(j,1,tot) P[j]=F[j];
		cnt=tot;
	}
	inc(i,1,cnt) ans+=P[i].area();
	printf("%.3lf",ans);
}
int main(){ 
	scanf("%d",&n);
	inc(i,1,n) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z),p[i].shake();
	solve();
}

半平面交

#include<bits/stdc++.h>
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;i++)
using namespace std;
const int MAXN=505;
const double eps=1e-10;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=x*10+ch-'0',ch=getchar();}
	return f*x;
}
int n,m,cnt;
struct point{
	double x,y;
	point operator+(const point a){return (point){x+a.x,y+a.y};}
	point operator-(const point a){return (point){x-a.x,y-a.y};}
	point operator*(double a){return (point){x*a,y*a};}
	double crs(point a){return x*a.y-y*a.x;}
}p[MAXN];
struct line{
	point s,t;
	double tang(){return atan2(t.y,t.x);}
}L[MAXN];
bool operator<(line x,line y){return x.tang()<y.tang();}
point insert(line l1,line l2){
	point u=l2.s-l1.s;
	double t=u.crs(l2.t)/l1.t.crs(l2.t);
	return l1.s+l1.t*t;
}
bool onleft(point a,line b){return b.t.crs(a-b.s)>eps;}
int half(){
	sort(L+1,L+cnt+1);
	int l=1,r=0,tot=0;
	point P[MAXN];
	line q[MAXN];
	q[++r]=L[1];
	inc(i,2,cnt){
	    while(r>l&&!onleft(P[r-1],L[i])) r--;
	    while(r>l&&!onleft(P[l],L[i])) l++;
	    q[++r]=L[i];
	    if(fabs(q[r].t.crs(q[r-1].t))<eps){
	    	r--;
	    	if(!onleft(P[r-1],L[i])) q[r]=L[i];
		}
		if(l<r) P[r-1]=insert(q[r],q[r-1]);
	}
	while(l<r&&!onleft(P[r-1],q[l])) r--;
	if(l+1>r) return 0;
	P[r]=insert(q[l],q[r]);
	inc(i,l,r) p[++tot]=P[i];
	return tot;
}
double solve(int num){
	double res=0;
	inc(i,1,num) res+=p[i].crs(p[i==num?1:i+1]);
	return res/2.0;
}
point pp[55];
int main(){
	n=read();
	inc(i,1,n){
		m=read();
		inc(j,1,m) pp[j].x=read(),pp[j].y=read();
		L[++cnt]=(line){pp[1],pp[1]-pp[m]};
		inc(j,2,m) L[++cnt]=(line){pp[j],pp[j]-pp[j-1]};
	} 
	int num=half();
	printf("%.3lf",solve(num)); 
}

最小圆覆盖

#include<bits/stdc++.h>
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;i++)
using namespace std;
const int N=1e6+5;
const double eps=1e-8;
int n;
struct point{
	double x,y;
	point(){}
	point(double xx,double yy){x=xx;y=yy;}
}p[N],o;
double r;
double sqr(double x){return x*x;}
double dis(point a,point b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
bool in_circle(point x){return dis(o,x)-r<eps;}
point operator+(point a,point b){return point(a.x+b.x,a.y+b.y);}
point operator-(point a,point b){return point(a.x-b.x,a.y-b.y);}
point operator*(point a,double t){return point(a.x*t,a.y*t);}
point operator/(point a,double t){return point(a.x/t,a.y/t);}
double dot(point a,point b){return a.x*b.x+a.y*b.y;}
double crs(point a,point b){return a.x*b.y-a.y*b.x;}
point rotate(point a){return point(a.y,-a.x);}
point cross(point p0,point v0,point p1,point v1){
	double t=crs(p1-p0,v1)/crs(v0,v1);
	return p0+v0*t;
}
point get_circle(point a,point b,point c){
	return cross((a+b)/2,rotate(b-a),(a+c)/2,rotate(c-a));
}
int main(){
	srand(time(NULL));
	scanf("%d",&n);
	inc(i,1,n) scanf("%lf%lf",&p[i].x,&p[i].y);
	random_shuffle(p+1,p+1+n);
	inc(i,1,n){
		if(in_circle(p[i])) continue;
		o=p[i],r=0;
		inc(j,1,i-1){
			if(in_circle(p[j])) continue;
			o=(p[i]+p[j])/2,r=dis(o,p[i]);
			inc(k,1,j-1){
				if(in_circle(p[k])) continue;
				o=get_circle(p[i],p[j],p[k]),r=dis(o,p[i]);
			}
		}
	}
	printf("%.10lf\n%.10lf %.10lf",sqrt(r),o.x,o.y);
}

平面最近点对

#include<bits/stdc++.h>
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;i++)
using namespace std;
const int N=2e5+5;
inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
} 
int n;
double ans=2e9;
struct point{
	double x,y;
}p[N]; 
bool cmpx(point a,point b){return a.x<b.x;}
bool cmpy(point a,point b){return a.y<b.y;}
double sqr(double x){return x*x;}
double dis(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
void solve(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	solve(l,mid),solve(mid+1,r);
	sort(p+l,p+r+1,cmpy);
	inc(i,l,r){
		for(re int j=i+1;j<=r&&p[j].y-p[i].y<ans;j++){
			ans=min(ans,dis(p[i],p[j]));
		}
	}
} 
int main(){
	n=read();
	inc(i,1,n) p[i].x=read(),p[i].y=read();
	sort(p+1,p+1+n,cmpx);
	solve(1,n);
	printf("%.4lf",ans);
}

闵可夫斯基和

#include<bits/stdc++.h>
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;i++)
#define dec(i,j,k) for(re int i=j;i>=k;i--)
#define db double
using namespace std; 
const int N=1e5+5;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=x*10+ch-'0',ch=getchar();}
	return f*x;
}
int n,m,q,tot;
struct node{
	db x,y;
	node(){}
	node(db xx,db yy){x=xx,y=yy;}
	node operator+(node a){return node(x+a.x,y+a.y);}
	node operator-(node a){return node(x-a.x,y-a.y);}
	db operator*(node a){return x*a.y-y*a.x;}
	db len(){return x*x+y*y;}
}a[N],b[N],c[N<<1],t[N],va[N],vb[N],bs,Q;
double slope(node a,node b){return (a.y-b.y)/(a.x-b.x);}
int st[N],top;
bool cmp1(node a,node b){return (a.y==b.y?a.y<b.y:a.x<b.x);}
bool cmp2(node a,node b){return a*b>0||(a*b==0&&a.len()<b.len());}
void convex(node *tmp,int &n){
	sort(tmp+1,tmp+1+n,cmp1);
	bs=tmp[1];st[top=1]=1;
	inc(i,1,n) tmp[i]=tmp[i]-bs;
	sort(tmp+2,tmp+1+n,cmp2);
	inc(i,2,n){
		while(top>1&&(tmp[i]-tmp[st[top-1]])*(tmp[st[top]]-tmp[st[top-1]])>=0) top--;
		st[++top]=i;
	}
	inc(i,1,top) tmp[i]=tmp[st[i]]+bs;
	n=top;
}
void merge(){
	inc(i,1,n-1) va[i]=a[i+1]-a[i];va[n]=a[1]-a[n];
	inc(i,1,m-1) vb[i]=b[i+1]-b[i];vb[m]=b[1]-b[m];
	c[tot=1]=a[1]+b[1];
	int ca=1,cb=1;
	while(ca<=n&&cb<=m) ++tot,c[tot]=c[tot-1]+(va[ca]*vb[cb]>=0?va[ca++]:vb[cb++]);
	while(ca<=n) ++tot,c[tot]=c[tot-1]+va[ca++];
	while(cb<=m) ++tot,c[tot]=c[tot-1]+vb[cb++];
}
int in(node p){
	if(p*c[1]>0||c[tot]*p>0) return 0;
	int x=lower_bound(c+1,c+1+tot,p,cmp2)-c-1;
	return (p-c[x])*(c[x%tot+1]-c[x])<=0;
}
int main(){
	n=read(),m=read(),q=read();
	inc(i,1,n) a[i].x=read(),a[i].y=read();
	convex(a,n);
	inc(i,1,m) b[i].x=-read(),b[i].y=-read();
	convex(b,m);
	merge();	
	convex(c,tot);
	bs=c[1];inc(i,1,tot) c[i]=c[i]-bs;
	inc(i,1,q){
		Q.x=read(),Q.y=read();
		printf("%d\n",in(Q-bs));
	}
}

动态闵可夫斯基和

#include<bits/stdc++.h>
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;i++)
#define dec(i,j,k) for(re int i=j;i>=k;i--)
#define ll long long
#define db double
#define pb push_back
#define mp make_pair
#define IT set<node>::iterator
using namespace std;
const int N=1e5+5;
const int M=5e5+5;
inline int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int T,top;
struct node{
    int x,y;
    node(){}
    node(int xx,int yy){x=xx,y=yy;}
}st[M],p[M];
bool cmp(node a,node b){
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
bool operator==(node a,node b){return a.x==b.x&&a.y==b.y;}
bool operator!=(node a,node b){return (a==b)^1;}
node operator+(node a,node b){return node(a.x+b.x,a.y+b.y);}
node operator-(node a,node b){return node(a.x-b.x,a.y-b.y);}
node operator*(node a,int t){return node(a.x*t,a.y*t);}
ll operator*(node a,node b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
ll operator^(node a,node b){return 1ll*a.x*b.x+1ll*a.y*b.y;}
int where(node a){
    if(a.x==0&&a.y==0) return 0;
    if(a.y>0&&a.x>=0) return 1;
    if(a.y<=0&&a.x>0) return 2;
    if(a.y<0&&a.x<=0) return 3;
    if(a.y>=0&&a.x<0) return 4;
    exit(1);
}
int cnt=0;
bool operator<(node a,node b){
    if(where(a)!=where(b)) return where(a)<where(b);
    ll d=a*b;
    if(d==0) return (a^a)<(b^b);
    return d<0;
}
bool operator<=(node a,node b){return a<b||a==b;}
set<node> s[N];
node t[M],sum[M];
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
int ch[M][2],fa[M],rt,sz,num[M];
int check(int x){return lc(fa[x])==x?0:1;}
void up(int x){sum[x]=sum[lc(x)]+t[x]*num[x]+sum[rc(x)];}
void rotate(int x){
    int y=fa[x],z=fa[y],k=check(x),w=ch[x][k^1];
    assert(x!=w);
    ch[y][k]=w,fa[w]=y;
    if(z) ch[z][check(y)]=x;
    fa[x]=z;
    ch[x][k^1]=y,fa[y]=x;
    up(y),up(x);
}
void splay(int x,int goal=0){
    while(fa[x]!=goal){
        int y=fa[x],z=fa[y];
        if(z!=goal){
            if(check(x)==check(y)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if(!goal) rt=x;
}
void debug(int x){
    if(!x) return;
    printf("%d %d %d %d %d %d %d %d\n",x,lc(x),rc(x),t[x].x,t[x].y,sum[x].x,sum[x].y,num[x]);
    debug(lc(x));
    debug(rc(x));
}
void insert(node a){
    int tmp=rt,p=0;
    while(tmp&&t[tmp]!=a) p=tmp,tmp=ch[tmp][t[tmp]<a];
    if(tmp) num[tmp]++,up(tmp);
    else{
        tmp=++sz;
        if(p) ch[p][t[p]<a]=tmp;
        fa[tmp]=p,sum[tmp]=t[tmp]=a;    
        num[tmp]=1;
    }
    splay(tmp);
}
int find(node a){
    int tmp=rt;
    while(tmp&&t[tmp]!=a) tmp=ch[tmp][t[tmp]<a];
    return tmp;
}
int fpre(){
    int tmp=ch[rt][0];
    while(rc(tmp)) tmp=rc(tmp);
    return tmp;
}
int fnxt(){
    int tmp=ch[rt][1];
    while(lc(tmp)) tmp=lc(tmp);
    return tmp;
}
void del(node a){
    int tmp=find(a);
    if(num[tmp]>1){
        num[tmp]--;    
        splay(tmp);
        return;
    }
    splay(tmp);
    if(!ch[tmp][0]){
        rt=ch[tmp][1];
        fa[rc(tmp)]=0;
        return;
    }
    if(!ch[tmp][1]){
        rt=ch[tmp][0];
        fa[lc(tmp)]=0;
        return;
    }
    int x=fpre(),y=fnxt();
    assert(x!=0);
    assert(y!=0);
    splay(x),splay(y,x);
    ch[y][0]=0;
    up(y),up(x);
}
bool in(node a){
    int tmp=rt;
    node pre=node(0,0);
    while(1){
        if(a<pre+sum[lc(tmp)]||(a.y==0&&t[tmp].y==0&&t[tmp].x<0)){
            if(!lc(tmp)) return false;
            tmp=lc(tmp);
        }
        else if(a<=pre+sum[lc(tmp)]+t[tmp]*num[tmp]) break;
        else{
            if(!rc(tmp)) return false;
            pre=pre+sum[lc(tmp)]+t[tmp]*num[tmp],tmp=rc(tmp);
        }
    } 
    node x=a-sum[lc(tmp)]-pre,y=a-sum[lc(tmp)]-t[tmp]*num[tmp]-pre;
    if(x*y==0) return (x^y)<=0;
    return x*y<=0;
}
IT pre(IT x,int id){
    IT res=x;
    if(res==s[id].begin()) res=s[id].end();
    return --res;
}
IT nxt(IT x,int id){
    IT res=++x;
    if(res==s[id].end()) res=s[id].begin();
    return res;
}
void ins(node a,int id){
    IT it=s[id].lower_bound(a);
    if(it==s[id].end()) it=s[id].begin();
    node x=(a-*it),y=(a-*pre(it,id));
    if(x*y>0) return;
    if(x*y==0&&(x^y)<=0) return;
    s[id].insert(a);
    if(x*y<0) del(*nxt(s[id].find(a),id)-*pre(s[id].find(a),id));
    it=nxt(s[id].find(a),id);
    while(s[id].size()>3&&(a-*it)*(a-*nxt(it,id))>=0){
        del(*nxt(it,id)-*it);
        s[id].erase(it);
        it=nxt(s[id].find(a),id);
    }
    insert(*it-a);
    it=pre(s[id].find(a),id);
    while(s[id].size()>3&&(a-*it)*(a-*pre(it,id))<=0){
        del(*it-*pre(it,id));
        s[id].erase(it);
        it=pre(s[id].find(a),id);
    }
    insert(a-*it);
}
int main(){
    T=read();
    while(T--){
        int n=read(),q=read();
        inc(i,1,n){
            int k=read();
            p[0].x=p[0].y=0;
            inc(j,1,k) p[j].x=read();
            inc(j,1,k) p[j].y=read();
            sort(p,p+1+k,cmp);
            st[top=1]=p[0];
            inc(j,1,k){
                while(top>=2&&1LL*(p[j].y-st[top-1].y)*(st[top].x-st[top-1].x)>=1LL*(st[top].y-st[top-1].y)*(p[j].x-st[top-1].x)) top--;
                st[++top]=p[j];
            }
            inc(j,1,top-1) s[i].insert(st[j]);
            st[top=1]=p[k];
            dec(j,k-1,0){
                while(top>=2&&1LL*(p[j].y-st[top-1].y)*(st[top].x-st[top-1].x)>=1LL*(st[top].y-st[top-1].y)*(p[j].x-st[top-1].x)) top--;
                st[++top]=p[j];
            }
            inc(j,1,top-1) s[i].insert(st[j]);
            for(IT it=s[i].begin();it!=s[i].end();it++){
                IT it1=nxt(it,i);
                insert(*it1-*it);
            }
        }
        inc(i,1,q){
            cnt++;
            int x=read(),y=read();
            if(in(node(x,y))) puts("YES");
            else puts("NO");
            x=read(),y=read();int id=read();
            ins(node(x,y),id);
        }
        inc(i,1,n) s[i].clear();
        inc(i,1,sz) num[i]=fa[i]=lc(i)=rc(i)=0,t[i]=node(0,0),sum[i]=node(0,0);sz=0;rt=0;
    }
}

标签：node,tmp,return,int,top,计算,几何,inc
From： https://www.cnblogs.com/ldxcaicai/p/16628349.html

相关文章

  • 快速计算 (a^b) mod n
    需求：计算(a^d)modn，其中a、d、n都是超大数，比如:a=29033793948611024383985226589380327268410365915345045221422018356137431660932535186202642526599446262022568978......
  • 【计算讲谈社】第十讲｜当云计算遇上碳中和
    碳中和的实现是一项复杂的系统工程。在碳中和的大背景下，云计算会和碳中和发生什么碰撞？阿里云【大咖说】全新子系列【计算讲谈社】第十讲《当云计算遇上碳中和》上线，阿里巴......
  • 第一章计算机系统概述
    1.1操作系统的概念（定义）功能和目标1.1.1操作系统的概念操作系统（OperatingSystem，OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源......
  • 如何把thinkphp5的项目迁移到阿里云函数计算来应对流量洪峰？
    原文链接：https://developer.aliyun.com/article/9827461.为什么要迁移到阿里云函数？我的项目是一个节日礼品领取项目，过节的时候会有短时间的流量洪峰。平时访问量很低。......
  • 使用函数计算自定义运行时快速部署一个 SpringBoot 项目 | 文末有礼
    作者：谱一段风华笔墨什么是函数计算阿里云函数计算FC是事件驱动的全托管计算服务。使用函数计算，您无需采购与管理服务器等基础设施，只需编写并上传代码。函数计算为您准......
  • 2022-08-26 js 乘法计算之小数失精
    例：0.55*100我们以为的运算结果：55实际上js的结果为：55.00000000000001这就是js的失精，简单来说就是js对算法的设计不够严谨导致的，具体原因可看这篇文章☞http://t.csdn.cn/......
  • Windows无法安装到这个磁盘, 这台计算机的硬件可能不支持启动到此磁盘
    仅记录，未验证1、legacy模式安装将磁盘的模式改为MBR，UEFI模式安装将磁盘模式改为GPT2、在错误提示界面：（1）按下“Shift+F10”快捷键（2）依次输入： diskpart lisdis seldi......
  • 22/8/25 深入理解计算机系统第九章 虚拟内存
    9.7案例：IntelCorei7/Linux内存系统见书5769.8Linux虚拟内存系统与进程相关的数据结构（比如：页表、task和mm结构、内核栈）对每个进程不同物理内存内核虚拟内存......
  • 计算机网络一轮
    第一章互联网和互连网：互连网：计算机网络多个计算机通过节点（节点可以是：集线器，交换机，路由器）多个计算机网络通过路由器连接，就是互连网互联网：只全球最大的，开放的，由......
  • 02379计算机网络管理复习汇总01
    第1章网络管理概论一、网络管理系统的层次结构：  二、网络管理框架的共同特点：管理功能分为了管理站（Manager）和代理（Agent）两局部；为了存储管理信息提供数据库支持，例如......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99