QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#420415 | #7906. Almost Convex | SunlightZero | WA | 7ms | 7828kb | C++14 | 4.0kb | 2024-05-24 17:48:57 | 2024-05-24 17:48:59 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using ld = long double;
constexpr size_t MAXN = 1e5 + 5;
constexpr ld pi = 3.14159265358979304228043196465883131283866529520193964395724800;
size_t n;
struct u256 {
u128 h, l;
u256(u128 h, u128 l): h(h), l(l) {}
u256(u128 x): h(0), l(x) {}
friend u256 operator*(u256 x, u256 y)
{
return {x.h * y.l + x.l * y.h, x.l * y.l};
}
friend bool operator<(u256 x, u256 y)
{
return x.h < y.h || (x.h == y.h && x.l < y.l);
}
friend bool operator==(u256 x, u256 y)
{
return x.h == y.h && x.l == y.l;
}
friend bool operator<=(u256 x, u256 y)
{
return x < y || x == y;
}
};
struct Point {
ll x, y;
friend Point operator-(Point u, Point v)
{
return {u.x - v.x, u.y - v.y};
}
friend bool operator==(Point u, Point v)
{
return u.x == v.x && u.y == v.y;
}
friend bool operator<(Point u, Point v)
{
return u.x < v.x || (u.x == v.x && u.y < v.y);
}
} points[MAXN], convex[MAXN], inner[MAXN];
size_t n_cvx, n_inner;
set<Point> st;
bool cmp1(Point u, Point v)
{
return u.x < v.x || (u.x == v.x && u.y > v.y);
}
ll cross(Point u, Point v)
{
return u.x * v.y - u.y * v.x;
}
struct Cmp {
Point o;
bool operator()(Point u, Point v)
{
return cross(u - o, v - o) > 0;
}
} cmp2;
size_t stk[MAXN], top;
i128 sqr(ll x)
{
return (i128) x * x;
}
ll dot(Point u, Point v)
{
return u.x * v.x + u.y * v.y;
}
ll len2(Point u)
{
return u.x * u.x + u.y * u.y;
}
int sgn(ll x)
{
return x > 0 ? 1 : -1;
}
void andrew()
{
sort(points + 1, points + n + 1, cmp1);
top = 0;
for (size_t i = 1; i <= n; i++)
{
while (top >= 2 && cross(points[stk[top]] - points[stk[top - 1]],
points[i] - points[stk[top]]) < 0)
{
top--;
}
stk[++top] = i;
}
for (size_t i = 1; i < top; i++)
{
convex[++n_cvx] = points[stk[i]];
st.insert(points[stk[i]]);
}
top = 0;
for (size_t i = n; i >= 1; i--)
{
while (top >= 2 && cross(points[stk[top]] - points[stk[top - 1]],
points[i] - points[stk[top]]) < 0)
{
top--;
}
stk[++top] = i;
}
for (size_t i = 1; i < top; i++)
{
convex[++n_cvx] = points[stk[i]];
st.insert(points[stk[i]]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (size_t i = 1; i <= n; i++)
{
cin >> points[i].x >> points[i].y;
}
andrew();
ull ans = 1;
for (size_t i = 1; i <= n; i++)
{
if (st.find(points[i]) == st.end())
{
inner[++n_inner] = points[i];
}
}
for (size_t i = 1; i <= n_cvx; i++)
{
Point a = convex[i], b = convex[i % n_cvx + 1];
cmp2.o = a;
sort(inner + 1, inner + n_inner + 1, cmp2);
ll cos_up = -1;
i128 cos_down = 1;
for (size_t k = 1; k <= n_inner; k++)
{
Point p = inner[k];
ll dot_prod = dot(p - b, a - b);
ll norm1 = len2(p - b), norm2 = len2(a - b); // 1e12
i128 norm = (i128) norm1 * norm2; // 1e24
if (sgn(dot_prod) > sgn(cos_up) ||
(sgn(dot_prod) == 1 && sgn(cos_up) == 1 &&
(u256) sqr(cos_up) * norm <= (u256) sqr(dot_prod) * cos_down) ||
(sgn(dot_prod) == -1 && sgn(cos_up) == -1 &&
(u256) sqr(dot_prod) * cos_down <= (u256) sqr(cos_up) * norm)
)
{
ans++;
cos_up = dot_prod; // 1e12
cos_down = norm;
}
}
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7712kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7828kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 5752kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7772kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 7ms
memory: 5860kb
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...
output:
24249
result:
wrong answer 1st numbers differ - expected: '718', found: '24249'