QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#420429 | #7906. Almost Convex | SunlightZero | WA | 0ms | 7692kb | C++14 | 3.0kb | 2024-05-24 18:08:06 | 2024-05-24 18:08:06 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
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;
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);
bool has_u = false;
Point u;
for (size_t k = 1; k <= n_inner; k++)
{
Point p = inner[k];
if (!has_u)
{
ans++;
has_u = true;
u = p;
continue;
}
if (cross(p - b, u - b) > 0)
{
ans++;
u = p;
}
}
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7672kb
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: -100
Wrong Answer
time: 0ms
memory: 7692kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
6
result:
wrong answer 1st numbers differ - expected: '5', found: '6'