QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87434 | #3184. Around the Track | ExplodingKonjac | WA | 2ms | 3780kb | C++17 | 3.9kb | 2023-03-12 21:27:18 | 2023-03-12 21:27:20 |
Judging History
answer
// test
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> Point;
typedef long long LL;
const int maxn=110;
bool operator != (Point b, Point c)
{
return (b.x!=c.x || b.y!=c.y);
}
double dis(Point b, Point c);
struct polygon
{
int n;
bool cannotdel[maxn];
Point p[maxn];
polygon():n(0){}
void read()
{
scanf("%d", &n);
for (int i=1; i<=n; ++i)
scanf("%d%d", &p[i].x, &p[i].y);
p[0]=p[n];
p[n+1]=p[1];
for (int i=1; i<=n; ++i) cannotdel[i]=false;
}
double track()
{
double ans=0;
for (int i=1; i<=n; ++i)
ans+=dis(p[i], p[i+1]);
return ans;
}
void del(int pos)
{
for (int i=pos; i<n; ++i)
{
p[i]=p[i+1];
cannotdel[i]=cannotdel[i+1];
}
--n;
p[n+1]=p[1];
p[0]=p[n];
}
void insert(int posl, int posr, vector<Point> &newp)
{
int m=posl+n-posr+1+newp.size();
for (int i=0; i<(n-posr+1); ++i)
{
p[m-i]=p[n-i];
cannotdel[m-i]=cannotdel[n-i];
}
n=m; m=newp.size();
for (int i=0; i<m; ++i)
{
p[posl+1+i]=newp[i];
cannotdel[posl+1+i]=true;
}
p[n+1]=p[1];
p[0]=p[n];
}
void print()
{
puts("======================");
for (int i=1; i<=n+1; ++i)
printf("%d %d\n", p[i].x, p[i].y);
}
};
polygon inner, outer;
Point pp[maxn];
Point globalps;
set<Point> innerpoint;
vector<Point> newp;
inline LL sqr(LL x)
{
return x*x;
}
LL det(Point b, Point c, Point o)
{
return (b.x-o.x)*(c.y-o.y)-(b.y-o.y)*(c.x-o.x);
}
double dis(Point b, Point c)
{
return sqrt(sqr(b.x-c.x)+sqr(b.y-c.y));
}
LL sdis(Point b, Point c)
{
return (sqr(b.x-c.x)+sqr(b.y-c.y));
}
bool intriangle(Point &b, Point &c, Point &d, Point &o)
{
return (abs(det(b, c, o))+abs(det(b, d, o))+abs(det(c, d, o)))==abs(det(b, c, d));
}
bool cmp(Point b, Point c)
{
LL tmp=det(b, c, globalps);
if (tmp!=0) return tmp<0;
return sdis(b, globalps)<sdis(c, globalps);
}
void convex(vector<Point> &p, Point &ps, Point &pf)
{
globalps=ps;
sort(p.begin(), p.end(), cmp);
int n=p.size();
for (int i=1; i<=n; ++i) pp[i]=p[i-1];
pp[++n]=pf;
pp[0]=ps;
int m=0;
for (int i=1; i<=n; ++i)
{
while (m>0 && det(pp[i], pp[m], pp[m-1])<0) --m;
pp[++m]=pp[i];
}
p.resize(m-1);
for (int i=1; i<m; ++i) p[i-1]=pp[i];
}
void solve()
{
for (int i=1; i<=inner.n; ++i)
innerpoint.insert(inner.p[i]);
while (1)
{
bool flag=false;
for (int i=1; i<=inner.n; ++i)
if (!inner.cannotdel[i] && det(inner.p[i+1], inner.p[i-1], inner.p[i])<0)
{
newp.clear();
for (int j=1; j<=outer.n; ++j)
if (intriangle(inner.p[i-1], inner.p[i], inner.p[i+1], outer.p[j]))
if (innerpoint.count(outer.p[j])==0)
newp.push_back(outer.p[j]);
if (newp.size()==0) { flag=true; inner.del(i); break; }
convex(newp, inner.p[i-1], inner.p[i+1]);
flag=true;
for (auto &p:newp)
if (innerpoint.count(p)) { flag=false; break; }
if (!flag) continue;
for (auto &p:newp) innerpoint.insert(p);
inner.insert(i-1, i+1, newp);
}
if (!flag) break;
}
printf("%.7lf\n", inner.track());
}
int main()
{
inner.read();
outer.read();
solve();
return 0;
}
/*
9
2 3
5 5
5 3
3 3
6 1
6 6
1 6
1 1
4 1
4
0 0
7 0
7 7
0 7
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3564kb
input:
3 1 1 2 1 1 2 3 0 0 4 0 0 4
output:
3.4142136
result:
ok found '3.4142136', expected '3.4142136', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
5 1 1 5 1 5 5 3 3 1 5 4 0 0 6 0 6 6 0 6
output:
16.0000000
result:
ok found '16.0000000', expected '16.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
5 1 1 5 1 5 5 3 3 1 5 5 0 0 6 0 6 6 3 4 0 6
output:
16.4721360
result:
ok found '16.4721360', expected '16.4721360', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
5 2 2 6 2 6 6 4 4 2 6 4 0 0 8 0 8 8 0 8
output:
16.0000000
result:
ok found '16.0000000', expected '16.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
5 2 2 6 2 6 6 4 4 2 6 5 0 0 8 0 8 8 4 5 0 8
output:
16.4721360
result:
ok found '16.4721360', expected '16.4721360', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
12 1 1 1 4 -1 4 -1 1 -4 1 -4 -1 -1 -1 -1 -4 1 -4 1 -1 4 -1 4 1 12 2 2 2 5 -2 5 -2 2 -5 2 -5 -2 -2 -2 -2 -5 2 -5 2 -2 5 -2 5 2
output:
25.8885438
result:
ok found '25.8885438', expected '25.8885438', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
8 1 1 15 1 15 7 14 7 14 2 2 2 2 7 1 7 15 0 0 16 0 16 8 13 8 12 4 11 6 10 3 9 6 8 5 7 6 6 3 5 6 4 4 3 8 0 8
output:
43.6832385
result:
ok found '43.6832385', expected '43.6832385', error '0.0000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
8 1 1 15 1 15 7 14 7 14 2 2 2 2 7 1 7 15 0 0 16 0 16 8 13 8 12 4 11 8 10 3 9 8 8 5 7 8 6 3 5 8 4 4 3 8 0 8
output:
43.6832385
result:
ok found '43.6832385', expected '43.6832385', error '0.0000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
8 1 1 15 1 15 7 14 7 14 2 2 2 2 7 1 7 15 0 0 16 0 16 8 13 8 12 4 11 7 10 3 9 7 8 5 7 7 6 3 5 7 4 4 3 8 0 8
output:
43.6832385
result:
ok found '43.6832385', expected '43.6832385', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
12 1 1 10 1 10 6 9 6 9 2 6 2 6 4 5 4 5 2 2 2 2 6 1 6 12 0 0 11 0 11 7 8 7 8 3 7 3 7 5 4 5 4 3 3 3 3 7 0 7
output:
33.1529824
result:
ok found '33.1529824', expected '33.1529824', error '0.0000000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
7 1 1 5 1 5 19 4 2 3 18 2 2 1 19 9 0 0 6 0 6 20 5 20 4 3 3 19 2 3 1 20 0 20
output:
102.1290318
result:
ok found '102.1290318', expected '102.1290318', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3708kb
input:
12 1 1 12 1 12 5 11 5 11 2 8 2 8 6 7 6 7 2 2 2 2 5 1 5 16 0 0 13 0 13 9 4 9 4 4 5 4 5 8 10 8 10 3 9 3 9 7 6 7 6 3 3 3 3 6 0 6
output:
36.7966913
result:
ok found '36.7966913', expected '36.7966913', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
12 1 1 12 1 12 5 11 5 11 2 8 2 8 6 7 6 7 2 2 2 2 5 1 5 12 0 0 13 0 13 9 4 9 4 4 5 4 5 8 6 8 6 3 3 3 3 6 0 6
output:
33.5214513
result:
ok found '33.5214513', expected '33.5214513', error '0.0000000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3572kb
input:
8 1 3 4 2 4 1 5 4 6 4 3 5 3 6 2 3 4 0 0 7 0 7 7 0 7
output:
14.4222051
result:
ok found '14.4222051', expected '14.4222051', error '0.0000000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
8 1 2 2 1 4 3 4 5 5 5 4 6 2 4 2 2 4 2 0 6 4 4 7 0 3
output:
12.9574173
result:
ok found '12.9574173', expected '12.9574173', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
8 2 2 4 2 6 4 5 5 5 4 3 4 1 2 2 1 4 3 0 7 4 4 6 0 2
output:
12.9574173
result:
ok found '12.9574173', expected '12.9574173', error '0.0000000'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
12 1 3 4 2 9 2 9 1 10 4 10 9 11 9 8 10 3 10 3 11 2 8 2 3 4 0 3 9 0 12 9 3 12
output:
33.0451887
result:
ok found '33.0451887', expected '33.0451887', error '0.0000000'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
44 21 -7 21 5 20 5 20 -6 17 -6 17 4 16 4 16 -5 13 -5 13 3 12 3 12 -4 9 -4 9 2 8 2 8 -3 5 -3 5 1 4 1 4 -2 1 -2 1 0 -1 0 -1 -2 -4 -2 -4 1 -5 1 -5 -3 -8 -3 -8 2 -9 2 -9 -4 -12 -4 -12 3 -13 3 -13 -5 -16 -5 -16 4 -17 4 -17 -6 -20 -6 -20 5 -21 5 -21 -7 44 22 -8 22 6 19 6 19 -5 18 -5 18 5 15 5 15 -4 14 -4 ...
output:
200.7120664
result:
ok found '200.7120664', expected '200.7120664', error '0.0000000'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
47 23 -13 22 11 21 -12 20 10 19 -11 18 9 17 -10 16 8 15 -9 14 7 13 -8 12 6 11 -7 10 5 9 -6 8 4 7 -5 6 3 5 -4 4 2 3 -3 2 1 1 -2 0 0 -1 -2 -2 1 -3 -3 -4 2 -5 -4 -6 3 -7 -5 -8 4 -9 -6 -10 5 -11 -7 -12 6 -13 -8 -14 7 -15 -9 -16 8 -17 -10 -18 9 -19 -11 -20 10 -21 -12 -22 11 -23 -13 47 24 -14 22 12 21 -11...
output:
603.5146780
result:
ok found '603.5146780', expected '603.5146780', error '0.0000000'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
8 -10 0 -10 -10 0 -10 10 -10 10 0 10 10 0 10 -10 10 8 -20 0 -20 -20 0 -20 20 -20 20 0 20 20 0 20 -20 20
output:
80.0000000
result:
ok found '80.0000000', expected '80.0000000', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
8 0 10 -10 10 -10 0 -10 -10 0 -10 10 -10 10 0 10 10 8 -20 0 -20 -20 0 -20 20 -20 20 0 20 20 0 20 -20 20
output:
80.0000000
result:
ok found '80.0000000', expected '80.0000000', error '0.0000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
8 10 0 10 10 0 10 -10 10 -10 0 -10 -10 0 -10 10 -10 8 -20 0 -20 -20 0 -20 20 -20 20 0 20 20 0 20 -20 20
output:
80.0000000
result:
ok found '80.0000000', expected '80.0000000', error '0.0000000'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
8 0 -10 10 -10 10 0 10 10 0 10 -10 10 -10 0 -10 -10 8 -20 0 -20 -20 0 -20 20 -20 20 0 20 20 0 20 -20 20
output:
80.0000000
result:
ok found '80.0000000', expected '80.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
4 -1000 -1000 0 0 1000 -1000 0 2000 50 1500 -1500 0 2500 -1500 -1500 -460 -730 -440 -720 -420 -710 -400 -700 -380 -690 -360 -680 -340 -670 -320 -660 -300 -650 -280 -640 -260 -630 -240 -620 -220 -610 -200 -600 -180 -590 -160 -580 -140 -570 -120 -560 -100 -550 -80 -540 -60 -530 -40 -520 -20 -510 0 -50...
output:
8560.6232978
result:
ok found '8560.6232978', expected '8560.6232978', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4 -1 -1 1 -1 1 1 -1 1 16 1 3 -1 3 -1 2 -2 1 -3 1 -3 -1 -2 -1 -1 -2 -1 -3 1 -3 1 -2 2 -1 3 -1 3 1 2 1 1 2
output:
8.0000000
result:
ok found '8.0000000', expected '8.0000000', error '0.0000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
8 0 -1 3 -3 1 0 3 3 0 1 -3 3 -1 0 -3 -3 20 0 -2 7 -9 5 -6 6 -5 9 -7 2 0 9 7 6 5 5 6 7 9 0 2 -7 9 -5 6 -6 5 -9 7 -2 0 -9 -7 -6 -5 -5 -6 -7 -9
output:
25.2982213
result:
ok found '25.2982213', expected '25.2982213', error '0.0000000'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3748kb
input:
5 5 5 3 3 1 5 1 1 5 1 5 0 0 6 0 6 6 3 4 0 6
output:
16.4721360
result:
ok found '16.4721360', expected '16.4721360', error '0.0000000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
12 45 45 135 45 135 108 243 108 162 45 315 45 270 225 189 225 234 117 135 117 162 225 45 108 16 0 0 138 0 138 93 143 98 148 72 211 99 155 44 342 -45 360 270 180 270 192 125 175 122 169 125 161 270 0 180 0 90
output:
1158.3531517
result:
ok found '1158.3531517', expected '1158.3531517', error '0.0000000'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
4 -360 180 -297 270 -360 315 -405 225 6 -45 45 -270 270 -90 288 -90 450 -450 495 -540 135
output:
351.5425972
result:
ok found '351.5425972', expected '351.5425972', error '0.0000000'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
49 0 -1 460 -1 460 0 450 999 440 0 430 999 420 0 410 999 400 0 390 999 380 0 370 999 360 0 350 999 340 0 330 999 320 0 310 999 300 0 290 999 280 0 270 999 260 0 250 999 240 0 230 999 220 0 210 999 200 0 190 999 180 0 170 999 160 0 150 999 140 0 130 999 120 0 110 999 100 0 90 999 80 0 70 999 60 0 50 ...
output:
46374.3044511
result:
ok found '46374.3044511', expected '46374.3044511', error '0.0000000'
Test #31:
score: -100
Wrong Answer
time: 2ms
memory: 3780kb
input:
50 -2255 1931 -2830 -3187 3406 -4113 -1883 -1838 2327 -1793 425 -1197 2782 -1197 -569 -601 -6 -1566 -1556 -1182 -793 124 3186 -187 481 523 1688 652 -1844 580 2726 1263 -1544 1419 2655 1961 -389 1916 2623 2899 -3785 4421 -4440 3211 -2902 3483 -4580 -3486 -2403 3382 -537 3211 425 2728 -1005 2345 -1696...
output:
73807.2340560
result:
wrong answer 1st numbers differ - expected: '67111.7337452', found: '73807.2340560', error = '0.0997665'