QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#772165 | #7906. Almost Convex | wangjunrui | WA | 1ms | 4132kb | C++14 | 2.8kb | 2024-11-22 17:17:39 | 2024-11-22 17:17:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e3 + 5;
typedef long long ll;
int n;
struct node
{
int x, y;
node(int _x = 0, int _y = 0) : x(_x), y(_y) {}
inline ll operator*(const node &rhs) const
{
return (ll)x * rhs.y - (ll)y * rhs.x;
}
inline double get()
{
return atan2(y, x);
}
inline node operator+(const node &rhs) const
{
return node(x + rhs.x, y + rhs.y);
}
inline node operator-(const node &rhs) const
{
return node(x - rhs.x, y - rhs.y);
}
} a[N];
int b[N], m;
int c[N], q;
bool vis[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
{
int x, y;
cin >> x >> y;
a[i] = node(x, y);
}
swap(a[1], *min_element(a + 1, a + 1 + n, [](node x, node y)
{
return x.x < y.x;
}));
sort(a + 2, a + 1 + n, [](node x, node y)
{
return (x - a[1]).get() < (y - a[1]).get();
});
b[m = 1] = 1;
for (int i = 2; i <= n; ++i)
{
while (m > 1 && (a[b[m - 1]] - a[b[m]]) * (a[i] - a[b[m]]) >= 0)
--m;
b[++m] = i;
}
while (m > 1 && (a[b[m - 1]] - a[b[m]]) * (a[1] - a[b[m]]) >= 0)
--m;
int cnt = 1;
for (int i = 1; i <= n; ++i)
vis[b[i]] = true;
for (int i = 1; i <= n; ++i)
{
if (vis[i])
continue;
q = 0;
for (int j = 1; j <= n; ++j)
{
if (vis[j] || i == j)
continue;
c[++q] = j;
}
sort(b + 1, b + 1 + m, [&](int x, int y)
{
return (a[x] - a[i]).get() < (a[y] - a[i]).get();
});
sort(c + 1, c + 1 + q, [&](int x, int y)
{
return (a[x] - a[i]).get() < (a[y] - a[i]).get();
});
for (int j = 1, l = 1, r = 1; j < m; ++j)
{
while (l <= q && (a[c[l]] - a[i]).get() <= (a[b[j]] - a[i]).get())
++l;
while (r <= q && (a[c[r]] - a[i]).get() < (a[b[j + 1]] - a[i]).get())
++r;
if (l < r)
{
bool flag = true;
ll area = abs((a[b[j]] - a[i]) * (a[b[j + 1]] - a[i]));
for (int k = l; k <= r; ++k)
{
ll x = abs((a[c[k]] - a[i]) * (a[c[k]] - a[b[j]]));
ll y = abs((a[c[k]] - a[i]) * (a[c[k]] - a[b[j + 1]]));
ll z = abs((a[c[k]] - a[b[j]]) * (a[c[k]] - a[b[j + 1]]));
if (x + y + z == area && x && y)
{
flag = false;
break;
}
}
cnt += flag;
}
else
++cnt;
}
bool flag = true;
ll area = abs((a[b[m]] - a[i]) * (a[b[1]] - a[i]));
for (int k = 1; k <= q; ++k)
{
if ((a[c[k]] - a[i]).get() > (a[b[m]] - a[i]).get()
|| (a[c[k]] - a[i]).get() < (a[b[1]] - a[i]).get())
{
ll x = abs((a[c[k]] - a[i]) * (a[c[k]] - a[b[m]]));
ll y = abs((a[c[k]] - a[i]) * (a[c[k]] - a[b[1]]));
ll z = abs((a[c[k]] - a[b[m]]) * (a[c[k]] - a[b[1]]));
if (x + y + z == area && x && y)
{
flag = false;
break;
}
}
}
cnt += flag;
}
cout << cnt << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4132kb
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: 1ms
memory: 4132kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
4
result:
wrong answer 1st numbers differ - expected: '5', found: '4'