QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#718999 | #7680. Subway | dezex | WA | 2ms | 4100kb | C++20 | 4.8kb | 2024-11-06 22:00:12 | 2024-11-06 22:00:13 |
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])
{
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3916kb
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: 3876kb
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: 4100kb
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: 3828kb
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: 1ms
memory: 3900kb
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: 3780kb
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: 3884kb
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: 3888kb
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: 3828kb
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: -100
Wrong Answer
time: 2ms
memory: 3820kb
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 105 -500051 5 0 77 -3 -1 95 -490050 95 -490049 95 -490049 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 97 -490046 97 -490045 97 -490045 97 -490044 98 -4...
result:
wrong answer Duplicated points on polyline 2.