QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87434#3184. Around the TrackExplodingKonjacWA 2ms3780kbC++173.9kb2023-03-12 21:27:182023-03-12 21:27:20

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-12 21:27:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3780kb
  • [2023-03-12 21:27:18]
  • 提交

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'