QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#420385 | #7906. Almost Convex | SunlightZero | WA | 5ms | 7804kb | C++14 | 3.3kb | 2024-05-24 16:59:58 | 2024-05-24 16:59:58 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u128 = __uint128_t;
using i128 = __int128_t;
constexpr size_t MAXN = 1e5 + 5;
size_t n;
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;
u128 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;
u128 cos_down = 1;
for (size_t k = 1; k <= n_inner; k++)
{
Point p = inner[k];
ll dot_prod = dot(a - b, p - b);
ll norm1 = len2(a - b), norm2 = len2(p - b);
if (sgn(dot_prod) > sgn(cos_up) ||
sgn(dot_prod) == 1 && sgn(cos_up) == 1 &&
sqr(dot_prod) * cos_down > sqr(cos_up) * norm1 * norm2 ||
sgn(dot_prod) == -1 && sgn(cos_up) == -1 &&
sqr(dot_prod) * cos_down < sqr(cos_up) * norm1 * norm2
)
{
ans++;
cos_up = dot_prod;
cos_down = norm1 * norm2;
}
}
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7804kb
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: 5608kb
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: 1ms
memory: 7660kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5668kb
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: 1ms
memory: 7748kb
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: 5ms
memory: 7776kb
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:
22415
result:
wrong answer 1st numbers differ - expected: '718', found: '22415'