QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#950016 | #4132. 逃考 | Wilderness | 100 ✓ | 435ms | 21084kb | C++14 | 9.4kb | 2025-03-24 18:26:47 | 2025-03-24 18:26:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ld=double;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline ld readld()
{
int x1=0,x2=0,t=1,k=1;
bool f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')k=-1;
ch=getchar();
}
while(isdigit(ch)||ch=='.')
{
if(ch=='.'){f=0,ch=getchar();continue;}
if(f)x1=(x1<<1)+(x1<<3)+(ch&15);
else x2=(x2<<1)+(x2<<3)+(ch&15),t=(t<<1)+(t<<3);
ch=getchar();
}
return k*(x1+(ld)x2/(ld)t);
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+48);
return;
}
namespace Polygon
{
const ld eps=1e-10,INF=1e10;
const int M=1e5+5;
int equal(ld x)
{
if(fabs(x)<eps)return 0;
return x<0?-1:1;
}
struct Point
{
ld x,y;int id;
Point(ld _x=0,ld _y=0,int _id=0){x=_x,y=_y,id=_id;}
inline void input(){x=readld(),y=readld();}
};
typedef Point Vector;
typedef vector<Point> VecP;
typedef vector<Vector> VecV;
Vector operator+(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator-(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator*(Vector A,ld p){return Vector(A.x*p,A.y*p);}
Vector operator/(Vector A,ld p){return Vector(A.x/p,A.y/p);}
bool operator<(const Vector&A,const Vector&B){return A.x<B.x||(A.x==B.x&&A.y<B.y);}
bool operator==(const Vector&A,const Vector&B){return !(equal(A.x-B.x)||equal(A.y-B.y));}
ld Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
ld Module(Vector A){return sqrt(A.x*A.x+A.y*A.y);}
ld Dist(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
ld Dist2(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
ld Angle(Vector A,Vector B){return acos(Dot(A,B)/(Module(A)*Module(B)));}
ld Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
ld Area(Vector A,Vector B,Vector C){return Cross(B-A,C-A)/2;}
Vector Projection(Vector A,Vector B){return B*(Dot(A,B)/(Module(B)*Module(B)));}
Vector Rotate(Vector A,ld rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}
bool VectorParallel(Vector A,Vector B){return !equal(Cross(A,B));}
Vector GetDirect(Point A,Point B){return Vector(B.x-A.x,B.y-A.y);}
ld Link(Point A,Point B,Point P){return Cross(GetDirect(A,B),GetDirect(A,P));}
Vector Normal(Vector A)
{
ld Mod=Module(A);
return Vector(-A.y/Mod,A.x/Mod);
}
struct Line
{
Point P;
Vector V;
Line(Point p=Point(),Vector v=Point()){P=p,V=v;}
bool operator==(const Line&B)const{return !equal(Cross(V,B.V))&&!equal(Cross(V,B.P-P));}
};
typedef vector<Line> VecL;
VecL::iterator operator+(VecL l,int pos){return l.begin()+pos;}
struct Segment
{
Point A,B;ld Angle;int id;
Segment(Point a=Point(),Point b=Point(),int _id=0){A=a,B=b,id=_id,Angle=atan2((b-a).y,(b-a).x);}
bool operator<(const Segment&S)const
{
if(!equal(Angle-S.Angle))return Link(A,S.A,S.B)>0;
return Angle<S.Angle;
}
};
typedef vector<Segment> VecS;
VecS::iterator operator+(VecS s,int pos){return s.begin()+pos;}
bool SegmentProperIntersection(Segment s1,Segment s2)
{
bool fg=1;
fg&=max(s1.A.x,s1.B.x)>=min(s2.A.x,s2.B.x);
fg&=max(s1.A.y,s1.B.y)>=min(s2.A.y,s2.B.y);
fg&=max(s2.A.x,s2.B.x)>=min(s1.A.x,s1.B.x);
fg&=max(s2.A.y,s2.B.y)>=min(s1.A.y,s1.B.y);
ld t1=Cross((s1.B-s1.A),(s2.A-s1.A)),t2=Cross((s1.B-s1.A),(s2.B-s1.A));
ld t3=Cross((s2.B-s2.A),(s1.A-s2.A)),t4=Cross((s2.B-s2.A),(s1.B-s2.A));
return fg&&equal(t1)*equal(t2)<=0&&equal(t3)*equal(t4)<=0;
}
bool LineParallel(Line l1,Line l2){return VectorParallel(l1.V,l2.V);}
Point GetSegIntersection(Segment s1,Segment s2)
{
ld t1=Link(s1.A,s2.B,s1.B),t2=Link(s1.A,s2.A,s1.B);
return Point((t1*s2.A.x-t2*s2.B.x)/(t1-t2),(t1*s2.A.y-t2*s2.B.y)/(t1-t2));
}
Point GetLineIntersection(Line l1,Line l2)
{
Vector tv=l1.P-l2.P;
ld tp=Cross(l2.V,tv)/Cross(l1.V,l2.V);
return l1.P+l1.V*tp;
}
ld GetPointLineDist(Point P,Line l)
{
Vector tv=P-l.P;
return fabs(Cross(tv,l.V))/Module(l.V);
}
ld GetPointSegDist(Point P,Segment l)
{
if(l.A==l.B)return Module(P-l.A);
Vector u=l.B-l.A,v=P-l.A,w=P-l.B;
if(equal(Dot(u,v))<0)return Module(v);
if(equal(Dot(u,w))>0)return Module(w);
return fabs(Cross(u,v))/Module(u);
}
Point GetLineProjection(Point P,Line l)
{
Vector tv=P-l.P;
return l.P+l.V*(Dot(l.V,P-l.P)/Module(l.V));
}
bool OnSegment(Point P,Segment s){return equal(Cross(s.A-P,s.B-P))==0&&equal(Dot(s.A-P,s.B-P))<0;}
bool OnRightSegment(Point P,Segment s){equal(Cross(P-s.A,s.B))>0;}
ld PolygonArea(int n,vector<Point>p)
{
ld S=0;
for(int i=2;i<n;++i)S+=(Cross(p[i]-p[1],p[i+1]-p[1])/2.0);
return S;
}
inline int Andrew(int n,VecP p,VecP&stk)
{
sort(p.begin()+1,p.begin()+n+1);
if(n<3)return -1;
stk[1]=p[1],stk[2]=p[2];
int top=2;
for(int i=3;i<=n;++i)
{
while(top>1&&Link(stk[top-1],stk[top],p[i])<=0)--top;
stk[++top]=p[i];
}
stk[++top]=p[n-1];
for(int i=n-2;i;--i)
{
while(top>1&&Link(stk[top-1],stk[top],p[i])<=0)--top;
stk[++top]=p[i];
}
return top;
}
inline int Graham(int n,VecP p,VecP&stk)
{
auto Graham_cmp=[&](Point S,Point B)
{
if(S.x==B.x&&S.y==B.y)return false;
ld Jd=Cross(GetDirect(p[1],S),GetDirect(p[1],B));
if(Jd>0)return true;
return !Jd&&Dist(p[0],S)<=Dist(p[0],B);
};
sort(p.begin()+2,p.begin()+n+1,Graham_cmp);
stk[1]=p[1];
int top=1;
for(int i=2;i<=n;++i)
{
while(top>1&&Link(stk[top-1],stk[top],p[i])<=0)--top;
stk[++top]=p[i];
}
stk[top+1]=p[1];
return top;
}
inline ld HalfPlane(int n,VecS s)
{
sort(s.begin()+1,s.begin()+n+1);
n=unique(s.begin()+1,s.begin()+n+1,[&](Segment S1,Segment S2){return fabs(S1.Angle-S2.Angle)<=eps;})-s.begin()-1;
VecS st(n+1);
st[1]=s[1],st[2]=s[2];
int hd=1,tl=2;
for(int i=3;i<=n;++i)
{
while(hd<tl&&Link(GetSegIntersection(st[tl],st[tl-1]),s[i].A,s[i].B)<0)--tl;
while(hd<tl&&Link(GetSegIntersection(st[hd],st[hd+1]),s[i].A,s[i].B)<0)++hd;
st[++tl]=s[i];
}
while(hd<tl&&Link(GetSegIntersection(st[tl],st[tl-1]),st[hd].A,st[hd].B)<0)--tl;
while(hd<tl&&Link(GetSegIntersection(st[hd],st[hd+1]),st[tl].A,st[tl].B)<0)++hd;
int m=tl-hd+1;
VecP p(m+1);
for(int i=hd;i<tl;++i)p[i-hd+1]=GetSegIntersection(st[i],st[i+1]);
if(tl-hd>1)p[tl-hd+1]=GetSegIntersection(st[hd],st[tl]);
return PolygonArea(m,p);
}
}
using namespace Polygon;
struct edges
{
int to,nxt,val;
}edge[M<<1];
int hd[M],tot=0;
inline void addedge(int u,int v)
{
edge[++tot].nxt=hd[u];
edge[tot].to=v;
edge[tot].val=1;
hd[u]=tot;
return;
}
inline void HalfPlane_suibian_Version(int n,VecS s,int id)
{
sort(s.begin()+1,s.begin()+n+1);
n=unique(s.begin()+1,s.begin()+n+1,[&](Segment S1,Segment S2){return fabs(S1.Angle-S2.Angle)<=eps;})-s.begin()-1;
VecS st(n+1);
st[1]=s[1],st[2]=s[2];
int hd=1,tl=2;
for(int i=3;i<=n;++i)
{
while(hd<tl&&Link(GetSegIntersection(st[tl],st[tl-1]),s[i].A,s[i].B)<0)--tl;
while(hd<tl&&Link(GetSegIntersection(st[hd],st[hd+1]),s[i].A,s[i].B)<0)++hd;
st[++tl]=s[i];
}
while(hd<tl&&Link(GetSegIntersection(st[tl],st[tl-1]),st[hd].A,st[hd].B)<0)--tl;
while(hd<tl&&Link(GetSegIntersection(st[hd],st[hd+1]),st[tl].A,st[tl].B)<0)++hd;
if(tl-hd<=1)return;
for(int i=hd;i<=tl;++i)
{
addedge(id,st[i].id);
addedge(st[i].id,id);
}
return;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
bool vis[M];
int dis[M];
inline int Dijkstra(int s,int t)
{
for(int i=0;i<=t+1;++i)dis[i]=0x3f3f3f3f,vis[i]=0;
dis[s]=0;
q.push({0,s});
while(!q.empty())
{
int top=q.top().second;
q.pop();
if(vis[top])continue;
vis[top]=1;
for(int i=hd[top];i;i=edge[i].nxt)
{
int to=edge[i].to,val=edge[i].val;
if(dis[to]>dis[top]+val)
{
dis[to]=dis[top]+val;
if(!vis[to])q.push({dis[to],to});
}
}
}
return dis[t];
}
VecS s(M);
VecP p(M);
Point Ed,Young;
vector<bool>notEd(M);
inline Segment addline(ld A,ld B,ld C,int id){return Segment(Point(-C/(A*A+B*B)*A,-C/(A*A+B*B)*B),Point(B-C/(A*A+B*B)*A,-C/(A*A+B*B)*B-A),id);}
int main()
{
int T=read();
while(T--)
{
int n=read();
Ed.input(),Young.input();
if(!n){puts("0");continue;}
ld Dis=INF;
int id=0;
for(int i=1;i<=n;++i)
{
p[i].input();
if(p[i].x>Ed.x||p[i].y>Ed.y){notEd[i]=1;continue;}
ld t=Dist2(p[i],Young);
if(t<Dis)Dis=t,id=i;
}
for(int i=1;i<=n;++i)
{
if(notEd[i])continue;
int cnt=0;
s[++cnt]=addline(0,-1,Ed.y,n+1);
s[++cnt]=addline(0,1,0,n+1);
s[++cnt]=addline(1,0,0,n+1);
s[++cnt]=addline(-1,0,Ed.x,n+1);
for(int j=1;j<=n;++j)
{
if(j==i||notEd[j])continue;
ld A=2*(p[i].x-p[j].x),B=2*(p[i].y-p[j].y),C=p[j].x*p[j].x+p[j].y*p[j].y-p[i].x*p[i].x-p[i].y*p[i].y;
s[++cnt]=addline(A,B,C,j);
}
HalfPlane_suibian_Version(cnt,s,i);
}
write(Dijkstra(id,n+1)),puts("");
for(int i=1;i<M;++i)edge[i]={0,0,0},hd[i]=0,notEd[i]=0;
}
return 0;
}
//(2*x1-2*xi)*x+(2*y1-2*yi)*y+(xi*xi+yi*yi-x1*x1-y1*y1)>=0;
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 5ms
memory: 20360kb
input:
2 0 10 10 5 5 3 3 3 2 2 1 1 2 2 2 1
output:
0 1
result:
ok 2 lines
Test #2:
score: 10
Accepted
time: 27ms
memory: 19936kb
input:
1 67 9435 9681 4721 4843 5185 4697 5653 4554 6121 4411 6589 4268 7057 4125 7525 3982 7993 3839 8461 3696 8929 3553 9397 3410 4597 5435 4477 6030 4357 6625 4237 7220 4117 7815 3997 8410 3877 9005 3757 9600 5142 5421 5567 6002 5992 6583 6417 7164 6842 7745 7267 8326 7692 8907 8117 9488 5537 4936 6357 ...
output:
6
result:
ok single line: '6'
Test #3:
score: 10
Accepted
time: 63ms
memory: 19920kb
input:
3 36 9745 9171 4873 4580 4167 4700 3462 4815 2757 4930 2052 5045 1347 5160 642 5275 5766 4918 6660 5251 7554 5584 8448 5917 9342 6250 4320 4536 3768 4487 3216 4438 2664 4389 2112 4340 1560 4291 1008 4242 456 4193 4587 4780 4302 4975 4017 5170 3732 5365 3447 5560 3162 5755 2877 5950 2592 6145 2307 63...
output:
2 2 4
result:
ok 3 lines
Test #4:
score: 10
Accepted
time: 111ms
memory: 20524kb
input:
1 253 9369 9873 4680 4934 4874 5121 5064 5306 5254 5491 5444 5676 5634 5861 5824 6046 6014 6231 6204 6416 6394 6601 6584 6786 6774 6971 6964 7156 7154 7341 7344 7526 7534 7711 7724 7896 7914 8081 8104 8266 8294 8451 8484 8636 8674 8821 8864 9006 9054 9191 9244 9376 4451 5217 4218 5498 3985 5779 3752...
output:
7
result:
ok single line: '7'
Test #5:
score: 10
Accepted
time: 113ms
memory: 19752kb
input:
2 142 9306 9315 4650 4648 8460 4514 7543 6239 6060 1411 6951 5194 6337 4448 3700 8678 412 8483 4579 8598 1660 4373 7813 5263 7878 7782 3376 383 6608 3375 1208 7523 279 9148 1402 2080 59 5554 6680 7253 7202 286 918 8348 7634 1758 554 2314 8253 8983 7130 336 2367 3996 9070 1377 4372 4574 2140 4554 144...
output:
4 4
result:
ok 2 lines
Test #6:
score: 10
Accepted
time: 151ms
memory: 20852kb
input:
2 182 1548 9698 770 4842 1540 6653 860 7475 98 5098 984 8531 372 9148 249 1813 875 8382 1453 2470 1464 3608 1497 8459 965 2261 1464 4740 1296 3144 974 9366 510 5482 1180 5674 1169 4362 811 7700 300 2825 481 9388 276 5373 83 1545 975 6777 284 3019 882 2127 1495 1847 401 1588 942 1956 721 7587 68 5616...
output:
2 4
result:
ok 2 lines
Test #7:
score: 10
Accepted
time: 378ms
memory: 21084kb
input:
3 64 9428 9393 4711 4691 5175 4610 5636 4524 6097 4438 6558 4352 7019 4266 7480 4180 7941 4094 8402 4008 8863 3922 9324 3836 4313 3892 3912 3088 3511 2284 3110 1480 2709 676 4287 5109 3860 5522 3433 5935 3006 6348 2579 6761 2152 7174 1725 7587 1298 8000 871 8413 444 8826 17 9239 3916 4411 3118 4126 ...
output:
6 23 21
result:
ok 3 lines
Test #8:
score: 10
Accepted
time: 385ms
memory: 20672kb
input:
3 46 9613 9894 4800 4938 4308 2877 6282 5007 4901 7579 3871 1414 2182 9338 8619 1518 2697 2588 5338 862 9379 2341 2032 4238 723 1294 1807 2771 316 8365 2903 8683 6249 1985 2044 7215 6709 2717 4466 6965 260 232 7092 5396 2004 7846 8023 8119 6567 663 2687 2195 1376 3131 4529 1643 5548 7805 9083 2318 8...
output:
2 19 13
result:
ok 3 lines
Test #9:
score: 10
Accepted
time: 408ms
memory: 20888kb
input:
3 38 9558 9625 4782 4807 5085 4701 5391 4590 5697 4479 6003 4368 6309 4257 6615 4146 6921 4035 7227 3924 7533 3813 7839 3702 8145 3591 8451 3480 8757 3369 9063 3258 9369 3147 4526 5234 4273 5656 4020 6078 3767 6500 3514 6922 3261 7344 3008 7766 2755 8188 2502 8610 2249 9032 1996 9454 4948 3929 5117 ...
output:
2 13 16
result:
ok 3 lines
Test #10:
score: 10
Accepted
time: 435ms
memory: 19692kb
input:
3 109 9264 9189 4633 4592 4081 4407 3530 4220 2979 4033 2428 3846 1877 3659 1326 3472 775 3285 224 3098 4830 4304 5028 4014 5226 3724 5424 3434 5622 3144 5820 2854 6018 2564 6216 2274 6414 1984 6612 1694 6810 1404 7008 1114 7206 824 7404 534 7602 244 4286 4486 3940 4378 3594 4270 3248 4162 2902 4054...
output:
6 9 10
result:
ok 3 lines