QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#950016#4132. 逃考Wilderness100 ✓435ms21084kbC++149.4kb2025-03-24 18:26:472025-03-24 18:26:48

Judging History

This is the latest submission verdict.

  • [2025-03-24 18:26:48]
  • Judged
  • Verdict: 100
  • Time: 435ms
  • Memory: 21084kb
  • [2025-03-24 18:26:47]
  • Submitted

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