QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#483484#6745. Delete the Treeucup-team052#TL 0ms0kbC++239.4kb2024-07-18 17:52:272024-07-18 17:52:27

Judging History

你现在查看的是最新测评结果

  • [2024-07-18 17:52:27]
  • 评测
  • 测评结果：TL
  • 用时：0ms
  • 内存：0kb
查看
  • [2024-07-18 17:52:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define double long double
const double eps=1e-12;
int sgn(double x)
{
	if(x<-eps) return -1;
	else if(x>eps) return 1;
	else return 0;
}
struct Vec
{
	double x,y;
	Vec(double a=0,double b=0) {x=a,y=b;}
	double norm() {return x*x+y*y;}
	double abs() {return sqrt(x*x+y*y);}
};
Vec rdvec()
{
	double x,y;
	scanf("%Lf %Lf",&x,&y);
	return Vec(x,y);
}
Vec rot90(Vec v) {return Vec(v.y,-v.x);}
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (const Vec &x,const double y) {return Vec(x.x*y,x.y*y);}
Vec operator / (const Vec &x,const double y) {return Vec(x.x/y,x.y/y);}
double dis(const Vec &x,const Vec &y) {return (x-y).abs();}
double dis(const Vec &x) {return sqrt(x.x*x.x+x.y*x.y);}
void print(Vec x) {printf("%.2Lf %.2Lf\n",x.x,x.y);}
double cdot(const Vec &x,const Vec &y) {return x.x*y.x+x.y*y.y;}
double cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
int ccw(const Vec &x,const Vec &y,const Vec &z)
{
	int w=sgn(cross(y-x,z-x));
	if(w==1) return 1; // ccw
	else if(w==-1) return -1; // cw;
	else return 0; // coline
}
struct Seg
{
	Vec s,t; // two points
	Seg(Vec x,Vec y) {s=x,t=y;}
	Seg() {}
	Vec d() {return t-s;}
	Vec point(double p) {return s+(t-s)*p;}
};
int parallel(Seg p,Seg q) {return sgn(cross(p.d(),q.d()))==0;}
Vec proj(Seg l,Vec x)
{
	double p=cdot(l.t-l.s,x-l.s)/(l.t-l.s).norm();
	return l.point(p);
}
int isintersect(Seg p,Seg q)
{
	if(max(p.s.x,p.t.x)<min(q.s.x,q.t.x)) return 0;
	if(max(q.s.x,q.t.x)<min(p.s.x,p.t.x)) return 0;
	if(max(p.s.y,p.t.y)<min(q.s.y,q.t.y)) return 0;
	if(max(q.s.y,q.t.y)<min(p.s.y,p.t.y)) return 0;
	if(ccw(q.s,p.s,p.t)*ccw(q.t,p.s,p.t)==1) return 0;
	if(ccw(p.s,q.s,q.t)*ccw(p.t,q.s,q.t)==1) return 0;
	return 1;
}
Vec crosspoint(Seg p,Seg q)
{
	double A=cross(p.t-p.s,q.t-q.s);
	double B=cross(p.t-p.s,p.t-q.s);
	return q.s+(q.t-q.s)*(B/A);
}
// counter-clockwise halfplanes
// return counter-clockwise
vector<Vec> halfPlane(vector<Seg> v)
{
	sort(v.begin(),v.end(),[&](Seg x,Seg y){
		double ang1=atan2(x.d().y,x.d().x);
		double ang2=atan2(y.d().y,y.d().x);
		if(sgn(ang1-ang2)) return ang1<ang2;
		else return ccw(x.s,y.s,y.t)==1;
	});
	auto onRight=[&](Seg s,Vec x) {return ccw(s.s,x,s.t)>=0;};
	static Seg q[1005];
	static Vec p[1005];
	int l=0,r=0; q[0]=v[0];
	for(int i=1;i<(int)v.size();i++)
	{
		while(l<r&&onRight(v[i],p[r])) r--;
		while(l<r&&onRight(v[i],p[l+1])) l++;
		q[++r]=v[i];
		if(parallel(q[r],q[r-1]))
		{
			if(onRight(q[r],q[r-1].s)&&cdot(q[r].d(),q[r-1].d())<eps) return {};
			r--;
			if(!onRight(q[r],v[i].s)) q[r]=v[i];
		}
		if(l<r) p[r]=crosspoint(q[r],q[r-1]);
	}
	while(l<r&&onRight(q[l],p[r])) r--;
	if(r-l<=1) return {};
	p[l]=crosspoint(q[l],q[r]);
	return vector<Vec>(p+l,p+r+1);
}
int pointOnLine(const Seg &l,Vec p)
{
	if(p.x<min(l.s.x,l.t.x)-eps||p.x>max(l.s.x,l.t.x)+eps) return 0;
	if(p.y<min(l.s.y,l.t.y)-eps||p.y>max(l.s.y,l.t.y)+eps) return 0;
	return ccw(l.s,p,l.t)==0;
}
int pointInPolygon(const vector<Vec> &a,Vec p)
{
	for(int i=0;i<(int)a.size();i++)
	{
		if(pointOnLine(Seg(a[i],a[(i+1)%(int)a.size()]),p)) return 1;
	}
	int sum=0;
	for(int i=0;i<(int)a.size();i++)
	{
		Vec P=a[i],Q=a[(i+1)%(int)a.size()];
		int op=1;
		if(P.x>Q.x) swap(P,Q),op=-1;
		if(P.x<p.x-eps&&p.x-eps<Q.x)
		{
			if(ccw(P,p,Q)==-1) sum+=op;
		}
	}
	return sum==0?0:2;
}
int alo,r,d;
#define N 1005
int intersect(Vec x,Vec y)
{
	return 4*r*r+eps>=(x-y).norm();
}
int incir(Vec c,Vec v)
{
	return r*r+eps>=(c-v).norm();
}
int intersect(Vec c,vector<Vec> p)
{
	if(pointInPolygon(p,c)) return 1;
	for(auto v:p) if(incir(c,v)) return 1;
	for(int i=0;i<(int)p.size();i++)
	{
		Vec P=p[i],Q=p[(i+1)%(int)p.size()];
		Vec pr=proj(Seg(P,Q),c);
		if(sgn(cdot(P-pr,Q-pr))<=0)
		{
			if(incir(c,pr)) return 1;
		}
	}
	return 0;
}
int intersect(vector<Vec> p,vector<Vec> q)
{
	for(int i=0;i<(int)p.size();i++)
	{
		if(pointInPolygon(q,p[i])) return 1;
	}
	for(int i=0;i<(int)q.size();i++)
	{
		if(pointInPolygon(p,q[i])) return 1;
	}
	for(int i=0;i<(int)p.size();i++)
	{
		Vec P=p[i],Q=p[(i+1)%(int)p.size()];
		for(int j=0;j<(int)q.size();i++)
		{
			Vec A=q[j],B=q[(j+1)%(int)q.size()];
			if(isintersect(Seg(P,Q),Seg(A,B))) return 1;
		}
	}
	return 0;
}
Vec c[N]; int T[N];
Vec s[N],t[N]; int u[N],v[N];
Vec getcir(int id,int ti)
{
	double r=(double)(ti-u[id])/(v[id]-u[id]);
	return s[id]+(t[id]-s[id])*r;
}
int n,m,ans;
int cir_cir_intersect(Vec c1,Vec c2,int l1,int r1,int l2,int r2)
{
	int tl=max(l1,l2),tr=min(r1,r2);
	if(tl<=tr) return intersect(c1,c2);
	else return 0;
}
int cir_mov_intersect(Vec c,Vec s,Vec t,int l1,int r1,int l2,int r2)
{
	int tl=max(l1,l2),tr=min(r1,r2);
	if(tl==tr)
	{
		double r=(double)(tl-l2)/(r2-l2);
		Vec cl=s+(t-s)*r;
		return intersect(c,cl);
	}
	else if(tl<=tr)
	{
		Vec cl,cr;
		{
			double r=(double)(tl-l2)/(r2-l2);
			cl=s+(t-s)*r;
		}
		{
			double r=(double)(tr-l2)/(r2-l2);
			cr=s+(t-s)*r;
		}
		printf("%d %d : \n",tl,tr);
		print(cl),print(cr);
		if(intersect(c,cl)) return 1;
		if(intersect(c,cr)) return 1;
		Vec tv=rot90(cr-cl); tv=tv/tv.abs()*r;
		vector<Vec> pol={cl+tv,cr+tv,cr-tv,cl-tv};
		return intersect(c,pol);
	}
	else return 0;
}
signed main()
{
	cin>>alo>>r>>d;
	for(int i=1;i<=alo;i++)
	{
		int op=read();
		if(op==1) n++,c[n]=rdvec(),T[n]=read();
		else m++,s[m]=rdvec(),t[m]=rdvec(),u[m]=read(),v[m]=read();
	}
	ans+=m;
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
	{
		int tl=max(T[i]-d,T[j]-d);
		int tr=min(T[i]+d,T[j]+d);
		if(tl<=tr) ans+=intersect(c[i],c[j]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			{ // moving cir
				int hav=0;
				hav|=cir_cir_intersect(c[i],s[j],T[i]-d,T[i]+d,u[j]-d,u[j]);
				hav|=cir_cir_intersect(c[i],t[j],T[i]-d,T[i]+d,v[j],v[j]+d);
				hav|=cir_mov_intersect(c[i],s[j],t[j],T[i]-d,T[i]+d,u[j],v[j]);
				cout<<hav<<endl;
				ans+=hav;
			}
			{ // frame
				int hav=0;
				double tl=max(T[i]-d,u[j]-d);
				double tr=min(T[i]+d,v[j]+d);
				if(tl<=tr)
				{
					Vec cl=s[j],cr=t[j];
					hav|=intersect(c[i],cl);
					hav|=intersect(c[i],cr);
					Vec tv=rot90(cr-cl); tv=tv/tv.abs()*r;
					vector<Vec> pol={cl+tv,cr+tv,cr-tv,cl-tv};
					hav|=intersect(c[i],pol);
				}
				ans+=hav;
				cout<<hav<<endl;
			}
		}
	}
	// cir -> cir
	for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++)
	{
		int hav=0;
		hav|=cir_cir_intersect(s[i],s[j],u[i]-d,u[i],u[j]-d,u[j]);
		hav|=cir_cir_intersect(s[i],t[j],u[i]-d,u[i],v[j],v[j]+d);
		hav|=cir_cir_intersect(t[i],s[j],v[i],v[i]+d,u[j]-d,u[j]);
		hav|=cir_cir_intersect(t[i],t[j],v[i],v[i]+d,v[j],v[j]+d);
		hav|=cir_mov_intersect(s[i],s[j],t[j],u[i]-d,u[i],u[j],v[j]);
		hav|=cir_mov_intersect(t[i],s[j],t[j],v[i],v[i]+d,u[j],v[j]);
		hav|=cir_mov_intersect(s[j],s[i],t[i],u[j]-d,u[j],u[i],v[i]);
		hav|=cir_mov_intersect(t[j],s[i],t[j],v[j],v[j]+d,u[i],v[i]);
		{
			int tl=max(u[i],u[j]);
			int tr=min(v[i],v[j]);
			if(tl==tr)
			{
				Vec ci=getcir(i,tl),cj=getcir(j,tl);
				hav|=intersect(ci,cj);
			}
			else
			{
				Vec si=getcir(i,tl),ti=getcir(i,tr);
				Vec sj=getcir(j,tl),tj=getcir(j,tr);
				hav|=cir_mov_intersect(si,sj,ti-si+tj,tl,tr,tl,tr);
			}
		}
		ans+=hav;
	}
	// frame -> frame
	for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++)
	{
		int tl=max(u[i]-d,u[j]-d),tr=min(v[i]+d,v[j]+d);
		if(tl<=tr)
		{
			int hav=0;
			hav|=intersect(s[i],s[j]);
			hav|=intersect(s[i],t[j]);
			hav|=intersect(t[i],s[j]);
			hav|=intersect(t[i],t[j]);
			vector<Vec> poi,poj;
			{
				Vec tv=rot90(t[i]-s[i]); tv=tv/tv.abs()*r;
				poi={s[i]-tv,t[i]-tv,t[i]+tv,s[i]+tv};
			}
			{
				Vec tv=rot90(t[j]-s[j]); tv=tv/tv.abs()*r;
				poj={s[j]-tv,t[j]-tv,t[j]+tv,s[j]+tv};
			}
			hav|=intersect(s[i],poj);
			hav|=intersect(t[i],poj);
			hav|=intersect(s[j],poi);
			hav|=intersect(t[j],poi);
			hav|=intersect(poi,poj);
		}
	}
	// cir -> frame
	for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if(i!=j)
	{
		int hav=0;
		hav|=cir_cir_intersect(s[i],s[j],u[i]-d,u[i],u[j]-d,v[j]+d);
		hav|=cir_cir_intersect(s[i],t[j],u[i]-d,u[i],u[j]-d,v[j]+d);
		hav|=cir_cir_intersect(t[i],s[j],v[i],v[i]+d,u[j]-d,v[j]+d);
		hav|=cir_cir_intersect(t[i],t[j],v[i],v[i]+d,u[j]-d,v[j]+d);
		int tl=max(u[i],u[j]-d),tr=min(v[i],v[j]+d);
		if(tl<=tr)
		{
			Vec si=getcir(i,tl),ti=getcir(i,tr);
			hav|=intersect(si,s[j]);
			hav|=intersect(si,t[j]);
			hav|=intersect(ti,s[j]);
			hav|=intersect(ti,t[j]);
			vector<Vec> poi,poj;
			{
				Vec tv=rot90(ti-si); tv=tv/tv.abs()*r;
				poi={si-tv,ti-tv,ti+tv,si+tv};
			}
			{
				Vec tv=rot90(t[j]-s[j]); tv=tv/tv.abs()*r;
				poj={s[j]-tv,t[j]-tv,t[j]+tv,s[j]+tv};
			}
			hav|=intersect(si,poj);
			hav|=intersect(ti,poj);
			hav|=intersect(s[j],poi);
			hav|=intersect(t[j],poi);
			hav|=intersect(poi,poj);
		}
		ans+=hav;
	}
	cout<<ans<<endl;
	return 0;
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

5
1 2
1 3
1 4
4 5

output:

result:
English 繁體中文 简体中文

伺服器時間: 2024-12-03 00:33:27 | 開源專案