QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#573245 | #7906. Almost Convex | mhw | TL | 0ms | 4176kb | C++23 | 4.1kb | 2024-09-18 17:53:27 | 2024-09-18 17:53:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define il inline
const int N = 4e3 + 5;
const double eps = 1e-8;
il int sgn(double x)
{
// 进行判断, 提高精度
if (fabs(x) <= eps)
return 0; // x == 0, 精度范围内的近似相等
return x > 0 ? 1 : -1; // 返回正负
}
il bool eq(double a, double b) { return abs(a - b) < eps; } // ==
il bool le(double a, double b) { return a - b < eps; } // <=
il bool lt(double a, double b) { return a - b < -eps; } // <
typedef struct Point
{
int x, y;
// Point(double x = 0, double y = 0) : x(x), y(y) {} // 构造函数, 初始值为 0
// 重载运算符
// 点 - 点 = 向量 (向量AB = B - A)
Point operator-(const Point &B) const { return Point(x - B.x, y - B.y); }
// 点 + 点 = 点, 点 + 向量 = 向量, 向量 + 向量 = 向量
Point operator+(const Point &B) const { return Point(x + B.x, y + B.y); }
// 向量 · 向量 (点积)
double operator*(const Point &B) const { return x * B.x + y * B.y; }
// 向量 × 向量 (叉积)
double operator^(const Point &B) const { return x * B.y - y * B.x; }
// 判断大小, 一般用于排序
bool operator<(const Point &B) const { return x < B.x || (x == B.x && y < B.y); }
} Vector;
using Points = vector<Point>;
// 极角排序
// Need: (^, sgn)
// 基准点
Point p0;
il double theta(auto p) { return atan2(p.y, p.x); } // 求极角
void psort(Points &ps, Point c = p0) // 极角排序
{
sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
return lt(theta(p1 - c), theta(p2 - c));
});
}
// 凸包
// Andrew算法求凸包,最后一个点与第一个点重合
// Need: (^,-,<), sgn, le
il bool check(Point p, Point q, Point r) { return le(0, (q - p) ^ (r - q)); }
vector<Point> Andrew(Points poly)
{
int n = poly.size(), top = 0;
vector<int> stk(n + 10, 0), used(n + 10, 0);
sort(poly.begin(), poly.end());
stk[++top] = 0;
for (int i = 1; i < n; i++)
{
while (top > 1 && sgn((poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]])) <= 0)
used[stk[top--]] = 0;
used[i] = 1;
stk[++top] = i;
}
int tmp = top;
for (int i = n - 2; i >= 0; i--)
{
if (used[i]) continue;
while (top > tmp && sgn((poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]])) <= 0)
used[stk[top--]] = 0;
used[i] = 1;
stk[++top] = i;
}
vector<Point> a;
for (int i = 1; i <= top; i++) a.push_back(poly[stk[i]]);
return a;
}
const int mod = 1e9 + 7;
int hs(int x, int y)
{
return (x * 100000000 + y) %mod;
}
void solve()
{
int n;
cin >> n;
Points ans, p, temp;
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
p.push_back({a, b});
}
ans = Andrew(p);
unordered_map<int, int> mp;
for (auto [x, y]: ans) mp[hs(x, y)] = 1;
int res = 0;
for (int i = 0; i < n; i++)
{
auto [x, y] = p[i];
if (mp[hs(x, y)]) continue;
p0 = p[i];
temp.clear();
for (int j = 0; j < n; j++)
{
if (j != i) temp.push_back(p[j]);
}
sort(temp.begin(), temp.end(), [&](auto p1, auto p2) {
return lt(theta(p1 - p0), theta(p2 - p0));
});
int cnt = 0;
unordered_map<int, int> rk;
for (auto [xx, yy]: temp)
{
rk[hs(xx, yy)] = cnt;
cnt++;
}
if (cnt == 0) break;
for (int j = 0; j < (int)ans.size() - 1; j++)
{
auto p1 = ans[j], p2 = ans[j + 1];
if(rk[hs(p1.x, p1.y)] == (rk[hs(p2.x, p2.y)] + 1) % cnt || (rk[hs(p1.x, p1.y)] + 1) % cnt == rk[hs(p2.x, p2.y)]) res++;
}
}
cout << res + 1 << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
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: 4176kb
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: 3812kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3968kb
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: 3808kb
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...