QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303799 | #7906. Almost Convex | igor_the_creator | TL | 0ms | 4036kb | C++17 | 2.3kb | 2024-01-13 00:19:33 | 2024-01-13 00:19:35 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 5;
const int Mod = 998244353;
int xx, yy;
bool vis[N];
struct dot{
int x, y, id, idx;
}d[N], e[N], stac[N];
int cross(dot a, dot b, dot c) // ������
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp2(dot a, dot b)
{
if (atan2(a.y - yy, a.x - xx) != atan2(b.y - yy, b.x - xx)) {
return atan2(a.y - yy, a.x - xx) < atan2(b.y - yy, b.x - xx);
}
return a.x < b.x;
}
bool cmp1(dot a, dot b)
{
return (a.y == b.y) ? (a.x < b.x) : (a.y < b.y);
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n, top = 0, ans = 1;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> d[i].x >> d[i].y;
}
sort(d + 1, d + n + 1, cmp1);
stac[++top] = {d[1].x, d[1].y, 1, 1};
vis[1] = 1;
xx = d[1].x; yy = d[1].y;
sort(d + 2, d + n + 1, cmp2);
stac[++top] = {d[2].x, d[2].y, 2, 2};
vis[2] = 1;
for (int i = 1; i <= n; ++i) {
e[i] = {d[i].x, d[i].y, i, i};
}
for (int i = 3; i <= n; ++i) {
while (top >= 2 && cross(d[stac[top - 1].id], d[stac[top].id], d[i]) < 0) {
vis[stac[top].id] = 0;
--top;
}
stac[++top] = {d[i].x, d[i].y, i, top};
vis[stac[top].id] = 1;
}
for (int i = 1; i <= n; ++i) {
if (vis[i]) continue;
xx = d[i].x; yy = d[i].y;
sort(e + 1, e + n + 1, cmp2);
/*cout << xx << " , " << yy << "&&\n";
for (int j = 1; j <= n; ++j) {
cout << j << "(" << e[j].x << ", " << e[j].y << ") :" << atan2(e[j].y - yy, e[j].x - xx) << "##\n";
}*/
for (int j = 1; j < n; ++j) {
// cout << atan2(stac[j].y - yy, stac[j].x - xx) << " * " << atan2(stac[j + 1].y - yy, stac[j + 1].x - xx) << "\n";
// int res = abs(e[j].idx - e[j + 1].idx);
if (e[j].id == i) continue;
if (vis[e[j].idx] && (vis[e[j + 1].idx] || (e[j + 1].id == i && vis[e[j + 2].id]))) {
++ans;
/* cout << "(" << e[j].x << ", " << e[j].y << ") - ";
cout << "(" << d[i].x << ", " << d[i].y << ") - ";
cout << "(" << e[j + 1].x << ", " << e[j + 1].y << ")\n";*/
}
}
if (e[1].id == i) {
if (vis[e[2].id] && vis[e[n].id]) ++ans;
}
else if (e[n].id == i) {
if (vis[e[1].id] && vis[e[n - 1].id]) ++ans;
}
else {
if (vis[e[1].id] && vis[e[n].id]) ++ans;
}
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3948kb
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: 0ms
memory: 4036kb
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: 3628kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3876kb
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: 3976kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Time Limit Exceeded
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...