QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497451 | #7667. Crane Balancing | Max_s_xaM | WA | 0ms | 4004kb | C++14 | 3.5kb | 2024-07-29 08:34:49 | 2024-07-29 08:34:49 |
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 << 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'