题目链接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;
}