WA 6,7 求助
查看原帖
WA 6,7 求助
728448
mqmhaaaa1楼主2025/1/13 16:17
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
void write(ll x) {static ll sta[35];ll top = 0;do {sta[top++] = x % 10, x /= 10;} while (x);while (top) putchar(sta[--top] + 48);}
ll read() {ll x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') {  if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0'); ch = getchar(); }return x * w; }
const ll N=1e3+10,M=2e6+10,inf=0x3f3f3f3f;
ll to[M<<1],nxt[M<<1],w[M<<1],bh[N],tot=1;
ll head[N],st[N];
bool vis[N];
inline void add(ll u,ll v,ll z){
	to[++tot]=v;
	nxt[tot]=bh[u];
	w[tot]=z;
	bh[u]=tot;
//	cout<<u<<" "<<v<<" "<<z<<'\n';
	to[++tot]=u;
	nxt[tot]=bh[v];
	w[tot]=0;
	bh[v]=tot;
}
ll s,t;
inline bool bfs(){
	for(ll i=s;i<=t;i++){
		head[i]=bh[i];
		vis[i]=0;
		st[i]=0;
	}
	queue<ll>q;
	q.push(s);
	st[s]=0;vis[s]=1;
	while(q.size()){
		ll u=q.front();q.pop();
//		cout<<u<<'\n';
		vis[u]=0;
		for(ll i=bh[u];i;i=nxt[i]){
			ll v=to[i];
			if(w[i]&&!st[v]&&v!=s){
				st[v]=st[u]+1;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return st[t];
}
ll mxf=0;
ll dic(ll u,ll flow){
//	cout<<u<<" "<<flow<<'\n';
	vis[u]=1;
	if(u==t){
		mxf+=flow;return flow;
	}
	ll zy=0;
	for(ll i=head[u];i&&flow;i=nxt[i]){
		ll v=to[i];head[u]=i;
		if(w[i]&&(!vis[v]||v==t)&&st[v]==st[u]+1){
			ll jb=dic(v,min(w[i],flow));
			w[i]-=jb,w[i^1]+=jb;
			zy+=jb;flow-=jb;
			if(!flow)break;
		}
	}
	vis[u]=0;
	return zy;
}
struct zb{
	ld x,y;
};
struct hs{
	ld k,b;
	ll x;
};
inline hs geths(zb a,zb b){
	hs u;
//	cout<<u.x<<'\n';
	if(a.x!=b.x){
		u.k=1.0*(a.y-b.y)/1.0*(a.x-b.x);u.b=a.y-a.x*u.k;
	}else{
		u.x=a.x;
	}
	return u;
}
inline zb getzb(hs a,hs b){
	zb u;
	if(a.k==b.k){
		u.x=-inf,u.y=-inf;
		return u;
	}
	if(!a.x&&!b.x){
		u.x=(b.b-a.b)/(a.k-b.k);
		u.y=u.x*a.k+a.b;
	}else{
		if(a.x){
			u.x=a.x;
			u.y=u.x*b.k+b.b;
		}else{
			u.x=b.x;
			u.y=u.x*a.k+a.b;
		}
	}
	return u;
}
ld len(zb u,zb v){
	return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y));
}
struct yj{
	ll zt;ld x1,y1,x2,y2;ld x,y,r;
}jjbb[N];
ll cx,cy,n;
zb A,B,C,D;
inline bool pand(ll u,ll v){
	zb zxdu,zxdv;
	if(jjbb[u].zt==1){
		zxdu=(zb){1.0*jjbb[u].x,1.0*jjbb[u].y};
	}else{
		zxdu=getzb(geths((zb){jjbb[u].x1,jjbb[u].y1},(zb){jjbb[u].x2,jjbb[u].y2}),geths((zb){jjbb[u].x1,jjbb[u].y2},(zb){jjbb[u].x2,jjbb[u].y1}));
	}
	if(jjbb[v].zt==1){
		zxdv=(zb){jjbb[v].x,jjbb[v].y};
	}else{
		zxdv=getzb(geths((zb){jjbb[v].x1,jjbb[v].y1},(zb){jjbb[v].x2,jjbb[v].y2}),geths((zb){jjbb[v].x1,jjbb[v].y2},(zb){jjbb[v].x2,jjbb[v].y1}));
	}
	hs zxdhs=geths(zxdu,zxdv);
	ld jlu=0,jlv=0;
	if(jjbb[u].zt==1){
		jlu=jjbb[u].r;
	}else{
		zb jdu=getzb(zxdhs,geths((zb){jjbb[u].x1,jjbb[u].y1},(zb){jjbb[u].x1,jjbb[u].y2}));
		if(jdu.y>=jjbb[u].y1&&jdu.y<=jjbb[u].y2){
			jlu=len(jdu,zxdu);
		}else{
			jdu=getzb(zxdhs,geths((zb){jjbb[u].x1,jjbb[u].y1},(zb){jjbb[u].x2,jjbb[u].y1}));
			jlu=len(jdu,zxdu);
		}
	}
	
	if(jjbb[v].zt==1){
		jlv=jjbb[v].r;
	}else{
		zb jdv=getzb(zxdhs,geths((zb){jjbb[v].x1,jjbb[v].y1},(zb){jjbb[v].x1,jjbb[v].y2}));
		if(jdv.y>=jjbb[v].y1&&jdv.y<=jjbb[v].y2){
			jlv=len(jdv,zxdv);
		}else{
			jdv=getzb(zxdhs,geths((zb){jjbb[v].x1,jjbb[v].y1},(zb){jjbb[v].x2,jjbb[v].y1}));
			jlv=len(jdv,zxdv);
		}
	}
	if(jlu+jlv>=len(zxdu,zxdv))return 1;
	else return 0;
}
//zuoxia x1,y1 zuoshang x1,y2
//youxia x2,y1 youshang x2,y2
int main(){
	cx=read();cy=read();n=read();
	s=0;t=n*2+1;
	for(ll i=1;i<=n;i++){
		ll zt=read();
		jjbb[i].zt=zt;
		ll ui=i,uo=i+n;
		add(ui,uo,1);
		if(zt==1){
			jjbb[i].x=read(),jjbb[i].y=read(),jjbb[i].r=read();
			if((ld)abs(cy-jjbb[i].y)<=jjbb[i].r)add(uo,t,inf);
			if((ld)abs(jjbb[i].y-0)<=jjbb[i].r)add(s,ui,inf);
		}else{
			jjbb[i].x1=read();jjbb[i].y1=read();jjbb[i].x2=read();jjbb[i].y2=read();
			ld yy=(jjbb[i].y1+jjbb[i].y2)/2,jl=(ld)abs(jjbb[i].y2-jjbb[i].y1)/2;
			if((ld)abs(cy-yy)<=jl)add(uo,t,inf);
			if((ld)abs(yy-0)<=jl)add(s,ui,inf);
		}
	}
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=n;j++){
			if(i==j)continue;
			ll ui=i,uo=i+n,vi=j,vo=j+n;
			bool flag=pand(i,j);
			if(!flag)continue;
			add(uo,vi,inf);add(vo,ui,inf);
		}
	}
	while(bfs()){
		vis[t]=1;
		while(vis[t]){
			memset(vis,0,sizeof vis);
			dic(s,inf);
		}
	}
	write(mxf);
}
2025/1/13 16:17
加载中...