QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719049 | #7680. Subway | dezex | AC ✓ | 2ms | 4116kb | C++20 | 4.8kb | 2024-11-06 22:14:13 | 2024-11-06 22:14:20 |
Judging History
answer
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long double db;
const db eps = 1e-8;
typedef long long ll;
int sgn(db x)
{
if(fabs(x) < eps) return 0;
if(x < 0) return -1;
else return 1;
}
struct Point
{
db x,y;
Point(){}
Point(db x_, db y_):x(x_),y(y_){}
Point operator - (const Point& b){return Point(x-b.x,y-b.y);}
db operator ^ (const Point& b){
return x*b.y - y*b.x;
}
bool operator < (Point b) const {return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;}
bool operator == (Point b) const {return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;}
bool operator <= (Point b) const {return sgn(x-b.x)==0?sgn(y-b.y)<=0:x<b.x;}
Point operator *(const double &k)const{
return Point(x*k,y*k);
}
db distance(Point p){
return hypot(x-p.x,y-p.y);
}
void input(){
scanf("%Lf %Lf",&x,&y);
}
void output(){
printf("%.2f %.2f\n",x,y);
}
};
struct Line
{
Point s,e;
Line(){}
Line(Point s_, Point e_):s(s_),e(e_){}
Line(db a, db b, db c)
{
if(sgn(a) == 0)
{
s = Point(0, -c/b);
e = Point(1, -c/b);
} else if(sgn(b) == 0)
{
s = Point(-c/a, 0);
e = Point(-c/a, 1);
} else
{
s = Point(0, -c/b);
e = Point(1, (-c-a)/b);
}
}
Point crosspoint(Line v)
{
// printf("crossing:\n");
// s.output();e.output();
// printf("with\n");
// v.s.output();v.e.output();
db a1 = (v.e-v.s)^(s-v.s);
db a2 = (v.e-v.s)^(e-v.s);
// printf("a1:%.10Lf a2:%.10Lf\n",a1,a2);
// printf("res:");
// printf("%.2Lf %.2Lf\n",(s.x*a2-e.x*a1)/(a2-a1), (s.y*a2-e.y*a1)/(a2-a1));
// printf("a2-a1=%.10Lf\n",a2-a1);
// printf("a2-a1=%.10Lf\n",db((ll)a2-(ll)a1));
// printf("a2/(a2-a1)=%.10Lf\n",a2/(a2-a1));
return Point(s.x*(a2/(a2-a1))-e.x*(a1/(a2-a1)), s.y*(a2/(a2-a1))-e.y*(a1/(a2-a1)));
}
int linecrossseg(Line v)
{
// printf("crossing:\n");
// s.output();e.output();
// printf("with\n");
// v.s.output();v.e.output();
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
if((d1^d2)==-2) return 2;
return (d1==0||d2==0);
}
bool parallel(Line v){
return sgn((e-s)^(v.e-v.s)) == 0;
}
int relation(Point p){
int c = sgn((p-s)^(e-s));
if(c < 0)return 1;
else if(c > 0)return 2;
else return 3;
}
int linecrossline(Line v){
if((*this).parallel(v))
return v.relation(s)==3;
return 2;
}
db length(){
return s.distance(e);
}
db dispointtoline(Point p){
return fabs((p-s)^(e-s))/length();
}
};
db cross(Point A,Point B,Point C){
return (B-A)^(C-A);
}
struct Ele
{
Point s,e;
int cnt;
};
const int N=60;
Point u(10001,2);
Point v(-2, 10001);
int n;
Point p[N];
int a[N];
// Line l[N];
Point mid[N];
Ele e[N];
bool cmp(const Ele& a, const Ele& b)
{
return a.s < b.s;
}
int main()
{
scanf("%d",&n);
Line ax(Point(0,0), u);
for(int i=1;i<=n;i++)
{
p[i].input();
scanf("%d",&a[i]);
Point pt = ax.crosspoint(Line(p[i], p[i]-v));
e[i]=Ele{pt, p[i], a[i]};
// l[i]=Line(pt, p[i]);
};
sort(e+1,e+n+1,cmp);
for(int i=1;i<=n;i++)
p[i]=e[i].e;
for(int i=1;i<=n;i++)
a[i]=e[i].cnt;
for(int i=2;i<=n;i++)
{
Point pt = p[i];
pt.y-=1;
if(pt == p[i-1])
{
pt.y += 0.5;
pt.x += v.x/2;
pt.y += v.y/2;
};
mid[i]=pt;
};
int mx=0;
for(int i=1;i<=n;i++)
mx=max(mx, a[i]);
printf("%d\n",mx);
for(int i=mx;i>=1;i--)
{
// 特殊情况 只有一个点
int st=1,ed=n;
while(a[st] < i) st++;
while(a[ed] < i) ed--;
vector<Point> ans;
if(st<ed)
{
ans.push_back(p[st]);
for(int j=st+1;j<=ed;j++)
{
ans.push_back(mid[j]-v*i);
if(a[j] >= i)
ans.push_back(p[j]);
else
ans.push_back(p[j] - v*i);
};
} else
{
if(st==1)
{
ans.push_back(p[1]);
ans.push_back(mid[2]-v*i);
} else
{
ans.push_back(mid[st]-v*i);
ans.push_back(p[st]);
}
}
printf("%u ",ans.size());
for(auto pt:ans)
printf("%.0Lf %.0Lf ",pt.x,pt.y);
printf("\n");
};
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 3 2 1 7 -20000 3 3 5 1 2 4 -10001 2 1 5 -9999 3 3
result:
ok ok Sum L = 8
Test #2:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
1 1 1 1
output:
1 2 1 1 2 -10001
result:
ok ok Sum L = 2
Test #3:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
1 1 1 50
output:
50 2 1 1 100 -500050 2 1 1 98 -490049 2 1 1 96 -480048 2 1 1 94 -470047 2 1 1 92 -460046 2 1 1 90 -450045 2 1 1 88 -440044 2 1 1 86 -430043 2 1 1 84 -420042 2 1 1 82 -410041 2 1 1 80 -400040 2 1 1 78 -390039 2 1 1 76 -380038 2 1 1 74 -370037 2 1 1 72 -360036 2 1 1 70 -350035 2 1 1 68...
result:
ok ok Sum L = 100
Test #4:
score: 0
Accepted
time: 2ms
memory: 4112kb
input:
50 662 -567 48 728 -120 7 307 669 27 -885 -775 21 100 242 9 -784 -537 41 940 198 46 736 -551 30 -449 456 16 -945 382 18 -182 810 49 213 187 44 853 245 48 617 -305 19 -81 261 3 617 208 8 -548 -652 6 -888 -667 14 -371 -812 43 202 -702 10 -668 -725 5 961 -919 33 -870 -697 50 428 810 29 560 405 7 348 -3...
output:
50 43 -870 -697 -725 -499670 -725 -499669 -684 -500588 -684 -500587 -583 -499320 -583 -499319 -568 -500776 -568 -500775 -479 -500488 -479 -500487 -458 -499226 -458 -499225 -448 -500703 -448 -500702 -399 -500228 -399 -500227 -369 -500307 -369 -500306 -362 -500770 -362 -500769 -349 -499595 -349 -49959...
result:
ok ok Sum L = 4534
Test #5:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
50 -772 697 1 -756 -909 1 659 923 1 850 471 1 260 -24 1 473 -639 1 -575 393 1 -466 197 1 333 -637 1 -192 -890 1 103 546 1 749 -723 1 -573 613 1 214 -138 1 277 928 1 266 291 1 911 275 1 -680 -67 1 69 190 1 -197 -795 1 684 618 1 729 -115 1 -658 -229 1 -595 -470 1 898 -172 1 401 81 1 133 685 1 223 400 ...
output:
1 99 -772 697 -754 -10911 -756 -909 -678 -10069 -680 -67 -664 -10084 -666 -82 -656 -10231 -658 -229 -593 -10472 -595 -470 -573 -9609 -575 393 -571 -9389 -573 613 -569 -10718 -571 -716 -530 -9164 -532 838 -528 -9112 -530 890 -464 -9805 -466 197 -387 -9294 -389 708 -344 -9544 -346 458 -302 -9105 -304 ...
result:
ok ok Sum L = 99
Test #6:
score: 0
Accepted
time: 1ms
memory: 4108kb
input:
50 -56 747 3 993 -490 4 930 -139 1 -298 -330 1 938 -351 5 -973 100 5 -472 44 4 345 628 5 481 -91 4 789 581 5 457 -29 4 871 -799 1 692 994 4 699 854 2 893 -33 1 -483 256 3 -962 -540 2 846 -893 1 830 609 5 845 -383 2 -552 -966 1 -544 -51 1 564 186 4 -615 -675 1 618 -911 3 -561 -302 4 -293 667 3 -334 -...
output:
5 95 -973 100 -952 -50546 -952 -50545 -878 -50619 -878 -50618 -832 -49625 -832 -49624 -782 -50631 -782 -50630 -627 -50807 -627 -50806 -605 -50681 -605 -50680 -551 -50308 -551 -50307 -542 -50972 -542 -50971 -534 -50057 -534 -50056 -473 -49750 -473 -49749 -462 -49962 -462 -49961 -354 -49837 -354 -4983...
result:
ok ok Sum L = 489
Test #7:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
50 600 997 5 -893 -204 3 408 443 1 -560 -748 7 -647 161 6 -285 -980 1 87 -582 7 -48 -721 7 997 285 2 -189 -728 8 525 222 4 -324 816 9 760 317 3 753 -480 10 -813 -921 3 -325 -875 8 -747 816 10 -627 605 7 775 786 6 136 -54 2 274 948 10 216 -113 7 924 68 3 101 576 8 60 -501 2 898 801 8 -767 -974 10 -99...
output:
10 75 -767 -974 -727 -99195 -747 816 -640 -100346 -640 -100345 -627 -99850 -627 -99849 -607 -99406 -607 -99405 -540 -100759 -540 -100758 -478 -100469 -478 -100468 -399 -99447 -399 -99446 -377 -100752 -377 -100751 -329 -100174 -329 -100173 -305 -100886 -305 -100885 -304 -99195 -304 -99194 -293 -10100...
result:
ok ok Sum L = 890
Test #8:
score: 0
Accepted
time: 2ms
memory: 3988kb
input:
50 24 -889 49 117 418 49 25 524 44 980 -416 43 -494 357 41 -287 -285 46 151 574 41 -289 68 49 -515 -540 41 -367 -178 47 -887 151 45 197 -272 47 714 724 45 -737 94 49 810 830 47 808 -695 41 537 -637 49 -142 -167 44 -749 -631 47 445 -444 42 801 910 43 59 363 42 -912 466 50 -649 -479 48 -958 -511 49 88...
output:
50 37 -912 466 -787 -499900 -787 -499899 -768 -500165 -868 -114 -686 -500435 -686 -500434 -649 -500682 -649 -500681 -637 -499957 -637 -499956 -549 -500530 -549 -500529 -515 -499242 -515 -499241 -488 -500189 -488 -500188 -415 -500591 -415 -500590 -394 -499694 -394 -499693 -386 -499185 -386 -499184 -2...
result:
ok ok Sum L = 4830
Test #9:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
50 151 -171 50 -367 -951 50 808 569 50 150 -618 50 27 -476 50 -846 729 50 549 -456 50 50 646 50 294 -70 50 -571 104 50 128 -265 50 913 -700 50 267 -965 50 896 846 50 -2 713 50 21 679 50 -515 975 50 168 180 50 -369 -98 50 676 115 50 643 -779 50 920 -237 50 -324 450 50 149 -378 50 -882 -602 50 -126 -7...
output:
50 99 -882 -602 -751 -499772 -851 279 -746 -499322 -846 729 -741 -499450 -841 601 -504 -500219 -604 -168 -471 -499947 -571 104 -444 -499744 -544 307 -415 -499076 -515 975 -401 -499124 -501 927 -374 -499271 -474 780 -269 -500149 -369 -98 -267 -501002 -367 -951 -235 -499995 -335 56 -224 -499601 -324 4...
result:
ok ok Sum L = 4950
Test #10:
score: 0
Accepted
time: 2ms
memory: 4116kb
input:
50 4 5 34 1 -5 24 -4 -4 32 -3 3 28 0 -1 21 1 -4 25 0 0 30 0 -4 42 -3 -2 44 -5 -3 37 4 -1 46 5 2 20 2 2 37 -2 5 35 -2 -1 39 2 4 32 -4 -3 42 0 3 32 3 5 47 -4 1 2 5 -1 17 -5 -4 5 -2 2 29 -5 1 11 2 -5 43 4 4 14 -5 0 9 0 -5 17 5 1 27 -3 0 24 -1 4 16 5 0 50 3 -2 18 1 -2 6 2 -1 29 -1 3 38 1 5 36 -3 1 28 -3...
output:
50 2 104 -495050 5 0 77 -3 -1 94 -485049 95 -490049 94 -485048 95 -490048 95 -490047 95 -490046 95 -490045 95 -490044 96 -490055 96 -490054 96 -490051 96 -490050 96 -490048 96 -490047 96 -490045 96 -490044 97 -490054 97 -490053 97 -490047 97 -490046 96 -485045 97 -490045 96 -485044 97 -490044 98 -4...
result:
ok ok Sum L = 4523
Test #11:
score: 0
Accepted
time: 1ms
memory: 4112kb
input:
50 2 0 2 2 -3 2 4 1 2 -3 -3 2 -5 1 2 5 3 2 -5 -3 2 -3 -2 2 2 -1 2 2 3 2 4 4 1 1 -4 1 5 -1 2 -4 1 2 3 -2 1 -1 2 2 5 -5 2 -2 1 2 -5 -1 2 -2 -1 2 -1 -2 2 5 5 1 0 -2 2 1 1 1 2 2 2 3 5 2 -2 -4 1 -3 5 1 4 2 2 -4 -4 2 -3 2 1 5 0 2 -2 -2 2 -4 4 1 -2 5 2 2 5 1 3 -5 2 -4 5 2 -5 5 2 -2 4 2 -5 -5 2 -2 2 2 -3 -4...
output:
2 97 -5 -5 -1 -20006 -5 -3 -1 -20004 -5 -1 -1 -20002 -5 1 -1 -19998 -5 5 0 -20007 -4 -4 0 -20002 -4 1 0 -19999 0 -19998 -1 -14997 -4 5 1 -20007 -3 -4 0 -15005 -3 -3 0 -15004 -3 -2 1 -20003 -3 0 1 -20001 1 -20000 1 -19998 1 -19997 2 -20007 2 -20006 2 -20005 -2 -2 1 -15003 -2 -1 2 -20002 -2 1 1 -15000...
result:
ok ok Sum L = 196
Test #12:
score: 0
Accepted
time: 2ms
memory: 4080kb
input:
50 4 3 49 -5 -3 49 0 -3 50 -2 -4 49 -5 -5 50 4 0 49 -1 -2 49 -2 0 49 1 2 50 -1 -5 50 -5 -1 50 -5 5 49 2 0 50 -2 -3 50 -4 -5 50 0 -2 50 -5 4 50 -1 1 49 -1 -4 49 -3 -1 49 1 -3 50 -4 1 50 0 5 50 1 -2 50 -1 5 50 4 2 50 4 -3 49 1 -4 49 -1 -1 49 -3 -5 50 4 -4 50 3 2 49 3 -3 49 0 2 50 -3 -4 49 5 -1 49 -3 5...
output:
50 95 -5 -5 95 -500054 95 -500053 95 -500052 -5 -1 95 -500047 -5 4 94 -495045 95 -500045 96 -500056 -4 -5 96 -500050 -4 1 96 -500047 -4 4 97 -500056 -3 -5 96 -495054 97 -500054 97 -500052 97 -500051 97 -500046 97 -500045 98 -500055 98 -500054 97 -495053 -2 -3 98 -500051 98 -500050 98 -500048 -2 3 99...
result:
ok ok Sum L = 4946
Test #13:
score: 0
Accepted
time: 2ms
memory: 3828kb
input:
50 114 514 30 115 514 41 116 514 6 117 514 49 118 514 10 119 514 49 120 514 1 121 514 7 122 514 3 123 514 4 124 514 1 125 514 12 126 514 15 127 514 16 128 514 34 129 514 24 130 514 49 131 514 43 132 514 25 133 514 12 134 514 26 135 514 13 136 514 12 137 514 15 138 514 7 139 514 25 140 514 5 141 514 ...
output:
49 27 117 514 216 -489536 216 -489535 217 -489536 119 514 218 -489536 218 -489535 219 -489536 219 -489535 220 -489536 220 -489535 221 -489536 221 -489535 222 -489536 222 -489535 223 -489536 223 -489535 224 -489536 224 -489535 225 -489536 225 -489535 226 -489536 226 -489535 227 -489536 227 -489535 22...
result:
ok ok Sum L = 4339
Test #14:
score: 0
Accepted
time: 2ms
memory: 3888kb
input:
50 191 981 19 191 980 41 191 979 20 191 978 14 191 977 2 191 976 49 191 975 40 191 974 3 191 973 20 191 972 6 191 971 13 191 970 4 191 969 4 191 968 47 191 967 32 191 966 11 191 965 34 191 964 30 191 963 3 191 962 16 191 961 24 191 960 30 191 959 34 191 958 31 191 957 24 191 956 29 191 955 42 191 95...
output:
49 2 288 -484073 191 976 2 286 -474072 191 976 17 191 968 284 -464078 285 -469078 284 -464077 285 -469077 284 -464076 285 -469076 284 -464075 285 -469075 284 -464074 285 -469074 284 -464073 285 -469073 284 -464072 285 -469072 284 -464071 191 976 69 191 942 282 -454103 283 -459103 282 -454102 283 ...
result:
ok ok Sum L = 4249
Test #15:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
50 -123 456 47 -122 457 35 -121 458 25 -120 459 35 -119 460 30 -118 461 33 -117 462 21 -116 463 31 -115 464 21 -114 465 35 -113 466 20 -112 467 17 -111 468 25 -110 469 3 -109 470 29 -108 471 35 -107 472 4 -106 473 44 -105 474 4 -104 475 28 -103 476 49 -102 477 9 -101 478 39 -100 479 9 -99 480 21 -98...
output:
50 31 -92 487 9 -499563 9 -499562 10 -499562 10 -499561 11 -499561 11 -499560 12 -499560 12 -499559 13 -499559 13 -499558 14 -499558 14 -499557 15 -499557 15 -499556 16 -499556 16 -499555 17 -499555 17 -499554 18 -499554 18 -499553 19 -499553 19 -499552 20 -499552 20 -499551 21 -499551 21 -499550 22...
result:
ok ok Sum L = 4710
Test #16:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
50 321 -525 46 322 -526 14 323 -527 16 324 -528 38 325 -529 22 326 -530 24 327 -531 48 328 -532 5 329 -533 7 330 -534 30 331 -535 25 332 -536 2 333 -537 13 334 -538 1 335 -539 33 336 -540 8 337 -541 9 338 -542 2 339 -543 29 340 -544 17 341 -545 41 342 -546 39 343 -547 9 344 -548 47 345 -549 47 346 -...
output:
50 2 458 -500613 358 -562 2 456 -490612 358 -562 73 327 -531 424 -480581 424 -480580 425 -480582 425 -480581 426 -480583 426 -480582 427 -480584 427 -480583 428 -480585 428 -480584 429 -480586 429 -480585 430 -480587 430 -480586 431 -480588 431 -480587 432 -480589 432 -480588 433 -480590 433 -4805...
result:
ok ok Sum L = 4578
Test #17:
score: 0
Accepted
time: 2ms
memory: 3828kb
input:
50 -444 -555 23 -445 -556 32 -446 -557 36 -447 -558 29 -448 -559 4 -449 -560 25 -450 -561 29 -451 -562 5 -452 -563 9 -453 -564 28 -454 -565 35 -455 -566 26 -456 -567 22 -457 -568 39 -458 -569 13 -459 -570 50 -460 -571 37 -461 -572 14 -462 -573 26 -463 -574 49 -464 -575 23 -465 -576 44 -466 -577 2 -4...
output:
50 59 -488 -599 -387 -500649 -387 -500648 -386 -500648 -386 -500647 -385 -500647 -385 -500646 -384 -500646 -384 -500645 -383 -500645 -383 -500644 -382 -500644 -382 -500643 -381 -500643 -381 -500642 -380 -500642 -380 -500641 -379 -500641 -379 -500640 -378 -500640 -378 -500639 -377 -500639 -377 -50063...
result:
ok ok Sum L = 4310
Test #18:
score: 0
Accepted
time: 2ms
memory: 4108kb
input:
50 -142 0 48 -143 1 22 -144 2 45 -145 3 9 -146 4 36 -147 5 46 -148 6 26 -149 7 26 -150 8 9 -151 9 19 -152 10 22 -153 11 14 -154 12 8 -155 13 20 -156 14 41 -157 15 47 -158 16 22 -159 17 50 -160 18 3 -161 19 12 -162 20 15 -163 21 32 -164 22 46 -165 23 45 -166 24 3 -167 25 27 -168 26 33 -169 27 17 -170...
output:
50 61 -189 47 -88 -500005 -88 -500004 -87 -500006 -87 -500005 -86 -500007 -86 -500006 -85 -500008 -85 -500007 -84 -500009 -84 -500008 -83 -500010 -83 -500009 -82 -500011 -82 -500010 -81 -500012 -81 -500011 -80 -500013 -80 -500012 -79 -500014 -79 -500013 -78 -500015 -78 -500014 -77 -500016 -77 -50001...
result:
ok ok Sum L = 4818
Test #19:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
12 1000 1000 50 1000 -1000 50 1000 999 50 999 1000 50 999 -1000 50 -999 1000 50 1000 -999 50 -999 -1000 50 -1000 1000 50 -1000 -1000 50 -1000 -999 50 -1000 999 50
output:
50 23 -1000 -1000 -901 -496049 -1000 -999 -900 -499052 -1000 999 -901 -494050 -1000 1000 -899 -501051 -999 -1000 -899 -499051 -999 1000 1099 -501051 999 -1000 1099 -499051 999 1000 1100 -501051 1000 -1000 1099 -496049 1000 -999 1100 -499052 1000 999 1099 -494050 1000 1000 23 -1000 -1000 -903 -48604...
result:
ok ok Sum L = 1150
Test #20:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
4 1000 1000 50 1000 -1000 50 -1000 1000 50 -1000 -1000 50
output:
50 7 -1000 -1000 -900 -499051 -1000 1000 1100 -501051 1000 -1000 1100 -499051 1000 1000 7 -1000 -1000 -902 -489050 -1000 1000 1098 -491050 1000 -1000 1098 -489050 1000 1000 7 -1000 -1000 -904 -479049 -1000 1000 1096 -481049 1000 -1000 1096 -479049 1000 1000 7 -1000 -1000 -906 -469048 -1000 1000 1...
result:
ok ok Sum L = 350
Extra Test:
score: 0
Extra Test Passed