QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497452 | #7667. Crane Balancing | Max_s_xaM | AC ✓ | 0ms | 3820kb | C++14 | 3.5kb | 2024-07-29 08:35:27 | 2024-07-29 08:35:27 |
Judging History
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'