QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#483484 | #6745. Delete the Tree | ucup-team052# | TL | 0ms | 0kb | C++23 | 9.4kb | 2024-07-18 17:52:27 | 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;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
5 1 2 1 3 1 4 4 5