开O2AC不开会寄求助(计算几何)
  • 板块学术版
  • 楼主剑雪清寒
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/11/3 18:15
  • 上次更新2023/10/27 04:24:41
查看原帖
开O2AC不开会寄求助(计算几何)
214728
剑雪清寒楼主2022/11/3 18:15

题目链接link 代码如下,求求帮忙看下(

#include <bits/stdc++.h>
#define eps 1e-7
using namespace std;
inline long long read() {
	long long x;bool f;char ch;
	for(f=0;!isdigit(ch=getchar());f=ch=='-');
	for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
	return f?-x:x;
}
inline void print(long long x,char las) {
	if(!x) {
		putchar(48),putchar(las);
		return ;
	}
	if(x<0) putchar('-'),x=-x;
	int ls[20],k=0;
	while(x) ls[++k]=x%10,x/=10;
	while(k) putchar(ls[k--]+48);
	putchar(las);
	return ;
}
struct node {
	double x,y,r;long long t;
	inline double len() {
		return sqrt(x*x+y*y);
	}
	inline bool operator!=(const node &ls) const {
		return x!=ls.x || y!=ls.y;
	}
	inline node operator+(const node &ls) const {
		return {x+ls.x,y+ls.y};
	}
	inline void operator+=(const node &ls) {
		x+=ls.x;
		y+=ls.y;
		return ;
	}
	inline node operator-(const node &ls) const {
		return {x-ls.x,y-ls.y};
	}
	inline void operator-=(const node &ls) {
		x-=ls.x;
		y-=ls.y;
		return ;
	}
	inline node operator*(const double &ls) const {
		return {x*ls,y*ls};
	}
	inline void operator*=(const double &ls) {
		x*=ls;
		y*=ls;
		return ;
	}
	inline node operator/(const double &ls) const {
		return {x/ls,y/ls};
	}
	inline void operator/=(const double &ls) {
		x/=ls;
		y/=ls;
		return ;
	}
	inline double operator*(const node &ls) const {
		return x*ls.y-y*ls.x;
	}
	inline double operator^(const node &ls) const {
		return x*ls.x+y*ls.y;
	}
}magic[201],spirit[201],tree[201];
inline bool ck(node ma,node sp,node tr) {
    double dist,dis1,dis2,dis3,dis4;
    dist=fabs((sp-ma)*(tr-ma)/(sp-ma).len());
    dis1=(tr-ma).len();dis3=sqrt(dis1*dis1-dist*dist);
    dis2=(tr-sp).len();dis4=sqrt(dis2*dis2-dist*dist);
    if(fabs(dis3+dis4-(sp-ma).len())>eps) dist=min(dis1,dis2);
    return dist<=tr.r;
}
struct edge {
    int to,name,lim;edge *next;
};
struct gra {
    int rs;edge rd[40400],*head[402];
    inline void add(int u,int v,int lim) {
        rd[rs].to=v;rd[rs].lim=lim;rd[rs].name=rs;rd[rs].next=head[u];head[u]=&rd[rs++];
    }
}g1,g2;
int n=read(),m=read(),k=read(),s,t;
bitset<201>is;int ct=0,dist[402],cnt[402],as;
inline void start() {
    for(int i=s;i<=t;i++) dist[i]=-1,cnt[i]=0;
    queue<int>que;que.push(s);dist[s]=0;cnt[0]=1;
    while(!que.empty()) {
        int x=que.front();que.pop();
        for(edge *i=g2.head[x];i;i=i->next) if(dist[i->to]==-1) dist[i->to]=dist[x]+1,cnt[dist[i->to]]++,que.push(i->to);
    }
    return ;
}
inline int ISAP(int x,int lim) {
    if(x==t) {
        as+=lim;
        return lim;
    }
    int used=0;
    for(edge *i=g1.head[x];i;i=i->next) {
        int nex=i->to;
        if(i->lim && dist[nex]+1==dist[x]) {
            int cost=ISAP(nex,min(i->lim,lim-used));
            if(cost) {
                i->lim-=cost;
                g2.rd[i->name].lim+=cost;
                used+=cost;
                if(used==cost) return used;
            }
        }
    }
    for(edge *i=g2.head[x];i;i=i->next) {
        int nex=i->to;
        if(i->lim && dist[nex]+1==dist[x]) {
            int cost=ISAP(nex,min(i->lim,lim-used));
            if(cost) {
                i->lim-=cost;
                g1.rd[i->name].lim+=cost;
                used+=cost;
                if(used==cost) return used;
            }
        }
    }
    cnt[dist[x]]--;
    if(!cnt[dist[x]]) dist[s]=n+m+1;
    cnt[++dist[x]]++;
    return used;
}
inline bool check(long long ti) {
    as=0;
    for(edge *i=g1.head[s];i;i=i->next) {
        int nex=i->to;
        i->lim=(ti/magic[nex].t)+1;g2.rd[i->name].lim=0;
        // print(ti/magic[nex].t,' ');
    }
    for(int i=1;i<=n;i++) {
        for(edge *j=g1.head[i];j;j=j->next) {
            j->lim=1;g2.rd[j->name].lim=0;
        }
    }
    for(edge *i=g2.head[t];i;i=i->next) {
        int nex=i->to;
        i->lim=0;g1.rd[i->name].lim=1;
    }
    start();
    while(dist[s]<n+m+1) ISAP(s,INT_MAX);
    return as==m;
}
int main() {
    s=0,t=n+m+1;
    for(int i=1;i<=n;i++) magic[i].x=read(),magic[i].y=read(),magic[i].r=read(),magic[i].t=read(),g1.add(s,i,0),g2.add(i,s,0);
    for(int i=1;i<=m;i++) spirit[i].x=read(),spirit[i].y=read(),g1.add(i+n,t,1),g2.add(t,i+n,0);
    for(int i=1;i<=k;i++) tree[i].x=read(),tree[i].y=read(),tree[i].r=read();
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if((spirit[j]-magic[i]).len()-magic[i].r>eps) continue;
            bool tag=false;
            for(int p=1;p<=k;p++) {
                if(ck(magic[i],spirit[j],tree[p])) {
                    tag=1;break;
                }
            }
            if(tag) continue;
            if(!is[j]) is[j]=1,ct++;
            g1.add(i,j+n,1),g2.add(j+n,i,0);
        }
    }
    if(ct<m) {
        print(-1,'\n');return 0;
    }
    long long l=0,r=INT_MAX,ans=0;
    while(l<=r) {
        long long mid=(l+r)>>1;
        if(check(mid)) {
            ans=mid;r=mid-1;
        }else l=mid+1;
    }
    print(ans,'\n');
	return 0;
}
2022/11/3 18:15
加载中...