QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497451#7667. Crane BalancingMax_s_xaMWA 0ms4004kbC++143.5kb2024-07-29 08:34:492024-07-29 08:34:49

Judging History

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

  • [2024-07-29 08:34:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4004kb
  • [2024-07-29 08:34:49]
  • 提交

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 << floor(max(L, 0.0)) << " .. inf\n";
    else cout << floor(max(L, 0.0)) << " .. " << ceil(R) << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3584kb

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: 4004kb

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: 4000kb

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: 3964kb

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: 3716kb

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: 3964kb

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: 3944kb

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: 3884kb

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: 3996kb

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: 3944kb

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: -100
Wrong Answer
time: 0ms
memory: 3892kb

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:

2.12597e+06 .. 3.35774e+06

result:

wrong answer 1st lines differ - expected: '2125968 .. 3357736', found: '2.12597e+06 .. 3.35774e+06'