QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497452#7667. Crane BalancingMax_s_xaMAC ✓0ms3820kbC++143.5kb2024-07-29 08:35:272024-07-29 08:35:27

Judging History

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

  • [2024-07-29 08:35:27]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3820kb
  • [2024-07-29 08:35:27]
  • 提交

answer

#include <iostream>
#include <cmath>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 110;

int n;

struct Point
{
    ll x, y;
    Point(ll _x = 0, ll _y = 0) : x(_x), y(_y) {}
    Point operator + (const Point& u) const { return Point(x + u.x, y + u.y); }
    Point operator - (const Point& u) const { return Point(x - u.x, y - u.y); }
}p[MAXN];

inline ll det(Point a, Point b) { return a.x * b.y - a.y * b.x; }

int main()
{
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n);
    for (int i = 1; i <= n; i++) Read(p[i].x), Read(p[i].y);
    lf sf = 0, dx = 0, dy = 0;
    for (int i = 2; i < n; i++)
    {
        ll cur = det(p[i] - p[1], p[i + 1] - p[1]);
        dx += (p[1].x + p[i].x + p[i + 1].x) * cur;
        dy += (p[1].y + p[i].y + p[i + 1].y) * cur;
        sf += cur;
    }
    dx /= sf * 3.0, dy /= sf * 3.0;
    sf = (sf < 0 ? -sf : sf) / 2.0;

    ll mx = -2e9, mn = 2e9;
    for (int i = 1; i <= n; i++)
    {
        if (p[i].y == 0) mx = max(mx, p[i].x), mn = min(mn, p[i].x);
    }
    lf L = -2e9, R = 2e9;
    if (mn == p[1].x && dx < mn) L = 2e9, R = -2e9;
    else if (mn < p[1].x)
    {
        L = max(L, sf * (dx - mn) / (mn - p[1].x));
    }
    else if (mn > p[1].x)
    {
        R = min(R, sf * (dx - mn) / (mn - p[1].x));
    }
    if (mx == p[1].x && dx > mx) L = 2e9, R = -2e9;
    else if (mx < p[1].x)
    {
        R = min(R, sf * (dx - mx) / (mx - p[1].x));
    }
    else if (mx > p[1].x)
    {
        L = max(L, sf * (dx - mx) / (mx - p[1].x));
    }
    if (L > R || R < 0) cout << "unstable\n";
    else if (R == 2e9) cout << (int)floor(max(L, 0.0)) << " .. inf\n";
    else cout << (int)floor(max(L, 0.0)) << " .. " << (int)ceil(R) << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

7
50 50
0 50
0 0
30 0
30 30
40 40
50 40

output:

0 .. 1017

result:

ok single line: '0 .. 1017'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

7
50 50
0 50
0 0
10 0
10 30
20 40
50 40

output:

unstable

result:

ok single line: 'unstable'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

4
-10 10
-10 0
0 0
0 10

output:

0 .. inf

result:

ok single line: '0 .. inf'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

7
50 30
50 25
30 20
30 0
0 0
0 20
20 20

output:

0 .. 409

result:

ok single line: '0 .. 409'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

7
-50 25
-30 20
-30 0
0 0
0 20
-20 20
-50 30

output:

0 .. 409

result:

ok single line: '0 .. 409'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

8
100 100
100 110
50 110
50 50
0 50
0 0
60 0
60 100

output:

0 .. 2125

result:

ok single line: '0 .. 2125'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

6
10 50
100 50
100 60
0 60
0 0
10 0

output:

unstable

result:

ok single line: 'unstable'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

6
0 60
0 0
10 0
10 50
100 50
100 60

output:

3750 .. inf

result:

ok single line: '3750 .. inf'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

7
-100 100
-10 60
-20 0
0 10
20 0
10 60
100 100

output:

0 .. 1500

result:

ok single line: '0 .. 1500'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

8
50 50
-100 50
-100 40
0 40
0 0
10 0
10 40
50 40

output:

710 .. 1363

result:

ok single line: '710 .. 1363'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

8
-300 500
-100 0
0 200
100 0
300 500
100 200
0 400
-100 200

output:

0 .. 40000

result:

ok single line: '0 .. 40000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

10
-400 800
200 400
100 200
0 400
-100 200
-300 500
-100 0
0 200
100 0
300 500

output:

0 .. 53889

result:

ok single line: '0 .. 53889'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

16
1000 1000
1000 1100
-2000 1100
-2000 1
0 1
0 0
10 0
10 1
100 1
100 0
110 0
110 1
200 1
200 0
210 0
210 1000

output:

2125968 .. 3357736

result:

ok single line: '2125968 .. 3357736'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

60
32 25
29 32
25 25
25 22
22 22
22 25
20 25
20 20
23 17
23 10
16 10
9 10
12 12
14 15
12 17
19 17
15 25
15 20
10 20
7 25
0 20
6 20
5 15
5 11
0 15
0 10
0 5
3 0
7 4
5 7
5 10
12 7
10 4
11 2
12 0
15 0
15 3
13 3
13 7
17 7
20 3
20 2
20 0
25 3
30 0
30 3
30 5
27 5
24 7
24 12
27 12
27 9
30 9
30 13
30 16
27 1...

output:

0 .. 2911

result:

ok single line: '0 .. 2911'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

62
32 25
29 32
25 25
25 22
22 22
22 25
20 25
20 20
23 17
23 10
16 10
9 10
12 12
14 12
12 17
19 17
15 25
15 20
10 20
7 25
0 20
6 20
5 15
5 11
0 15
-100 15
-100 10
0 10
0 5
3 0
7 4
5 7
5 10
12 7
10 4
11 2
12 0
15 0
15 3
13 3
13 7
17 7
20 3
20 2
20 0
25 3
30 0
30 3
30 5
27 5
24 7
24 12
27 12
27 9
30 9
...

output:

735 .. 22911

result:

ok single line: '735 .. 22911'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

62
-100 10
0 10
0 5
3 0
7 4
5 7
5 10
12 7
10 4
11 2
12 0
15 0
15 3
13 3
13 7
17 7
20 3
20 2
20 0
25 3
30 0
30 3
30 5
27 5
24 7
24 12
27 12
27 9
30 9
30 13
30 16
27 16
27 14
25 14
25 17
25 19
32 25
29 32
25 25
25 22
22 22
22 25
20 25
20 20
23 17
23 10
16 10
9 10
12 12
14 12
12 17
19 17
15 25
15 20
10...

output:

unstable

result:

ok single line: 'unstable'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

62
-10 10
0 10
0 5
3 0
7 4
5 7
5 10
12 7
10 4
11 2
12 0
15 0
15 3
13 3
13 7
17 7
20 3
20 2
20 0
25 3
30 0
30 3
30 5
27 5
24 7
24 12
27 12
27 9
30 9
30 13
30 16
27 16
27 14
25 14
25 17
25 19
32 25
29 32
25 25
25 22
22 22
22 25
20 25
20 20
23 17
23 10
16 10
9 10
12 12
14 11
12 17
19 17
15 25
15 20
10 ...

output:

0 .. 368

result:

ok single line: '0 .. 368'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

12
11 4
11 5
7 5
7 9
6 9
6 5
2 5
2 4
6 4
6 0
7 0
7 4

output:

0 .. 3

result:

ok single line: '0 .. 3'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

12
11 4
11 5
7 5
7 9
6 9
6 5
2 5
2 1
6 1
6 0
7 0
7 4

output:

3 .. 12

result:

ok single line: '3 .. 12'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

7
1500 100
0 1
-2000 100
-1 1
-1 0
1 0
1 1

output:

5 .. 6

result:

ok single line: '5 .. 6'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

100
21 18
18 18
18 16
16 16
15 15
17 15
16 13
13 13
13 15
15 17
15 18
12 18
12 16
11 14
11 10
7 10
7 13
5 15
7 18
4 18
3 16
3 14
0 8
1 8
1 3
0 1
0 0
1 0
1 1
2 2
3 2
2 1
2 0
3 1
4 2
4 3
3 4
3 3
2 3
2 5
4 5
5 4
5 3
6 2
5 1
5 0
8 0
7 1
7 2
8 3
7 4
6 4
7 5
7 6
8 6
8 5
9 5
10 6
10 4
9 3
10 2
9 1
10 0
11 ...

output:

0 .. 2018

result:

ok single line: '0 .. 2018'