QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#927977 | #4132. 逃考 | ANIG | 100 ✓ | 317ms | 4480kb | C++14 | 2.5kb | 2025-03-07 20:02:20 | 2025-03-07 20:02:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5;
const double eps=1e-12,pi=acos(-1);
struct node{
double x,y;
friend node operator-(node a,node b){
return {a.x-b.x,a.y-b.y};
}
friend node operator*(double a,node b){
return {a*b.x,a*b.y};
}
friend node operator+(node a,node b){
return {a.x+b.x,a.y+b.y};
}
}p[N],st,ed;
double dis(node a,node b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double jj(node x){
return atan2(x.y,x.x);
}
bool chk(double x){
return abs(x)<=eps;
}
double cro(node a,node b){
return a.x*b.y-a.y*b.x;
}
struct vec{
node a,b;
int bh;
friend bool operator<(vec a,vec b){
if(chk(jj(a.b-a.a)-jj(b.b-b.a)))return cro(a.a-b.a,b.b-b.a)<-eps;
return jj(a.b-a.a)<jj(b.b-b.a);
}
};
node jd(vec a,vec b){
double k=cro(a.a-b.a,b.b-b.a)/cro(b.b-b.a,a.b-a.a);
return a.a+k*(a.b-a.a);
}
bool chk(vec a,vec b,vec c){
auto x=jd(a,b);
return cro(x-c.a,c.b-c.a)>-eps;
}
double S(node a,node b,node c){
return cro(b-a,c-a)/2;
}
node rot(node a,double x){
return {a.x*cos(x)-a.y*sin(x),a.x*sin(x)+a.y*cos(x)};
}
vec zc(node a,node b){
node x=0.5*(a+b),tmp=rot(b-a,pi/2);
return {x,x+tmp};
}
vector<vec>q;
vec qs[N];
node g[N];
vector<int>e[N];
int n,hd,tl,d[N],t;
void solve(){
sort(q.begin(),q.end());
vector<vec>tmp;
double lst=1e9;
for(auto c:q){
if(chk(jj(c.b-c.a)-lst))continue;
lst=jj(c.b-c.a);
tmp.push_back(c);
}
q=tmp;
hd=1;tl=0;
for(auto c:q){
while(hd<tl&&chk(qs[tl-1],qs[tl],c))tl--;
while(hd<tl&&chk(qs[hd+1],qs[hd],c))hd++;
qs[++tl]=c;
}
while(hd<tl&&chk(qs[tl-1],qs[tl],qs[hd]))tl--;
}
deque<int>qq;
signed main(){
cin>>t;
while(t--){
cin>>n;
cin>>ed.x>>ed.y>>st.x>>st.y;
for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y,e[i].clear();
for(int i=1;i<=n;i++){
q.clear();
for(int j=1;j<=n;j++){
if(i==j)continue;
auto tmp=zc(p[i],p[j]);
tmp.bh=j;
q.push_back(tmp);
}
q.push_back({{0,0},{1,0},n+1});
q.push_back({{ed.x,0},{ed.x,1},n+1});
q.push_back({{ed.x,ed.y},{ed.x-1,ed.y},n+1});
q.push_back({{0,ed.y},{0,0},n+1});
solve();
for(int j=hd;j<=tl;j++)e[i].push_back(qs[j].bh);
}
memset(d,0x3f,sizeof(d));
int wz=1;
for(int i=2;i<=n;i++){
if(dis(p[i],st)<dis(p[wz],st))wz=i;
}
d[wz]=0;
qq.push_back(wz);
while(qq.size()){
int x=qq.front();
qq.pop_front();
for(auto c:e[x]){
if(d[c]>d[x]+1){
d[c]=d[x]+1;
qq.push_back(c);
}
}
}
cout<<d[n+1]<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 4096kb
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: 3ms
memory: 4352kb
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: 2ms
memory: 4096kb
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: 40ms
memory: 4480kb
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: 24ms
memory: 4096kb
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: 40ms
memory: 4352kb
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: 247ms
memory: 4480kb
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: 238ms
memory: 4352kb
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: 317ms
memory: 4352kb
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: 286ms
memory: 4480kb
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