QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#573412 | #7906. Almost Convex | rxzfn639 | TL | 0ms | 4164kb | C++23 | 3.9kb | 2024-09-18 18:38:24 | 2024-09-18 18:38:26 |
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;
}
Point temp[N];
void solve()
{ int o = 0;
int n;
cin >> n;
Points ans, p;
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];
int tn = 0;
for (int j = 0; j < n; j++)
{
o++;
if (j != i) temp[tn++] = p[j];
}
sort(temp, temp + tn, [&](auto p1, auto p2) {
return lt(theta(p1 - p0), theta(p2 - p0));
});
for (int j = 0; j < tn; j++)
{
o++;
auto p1 = temp[j], p2 = temp[(j + 1) % tn];
if(mp[hs(p1.x, p1.y)] && mp[hs(p2.x, p2.y)]) res++;
}
if (o > 200000 && n == 2000) cout << i << ' ' << o << endl;
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4020kb
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: 3948kb
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: 3852kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4164kb
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: 3780kb
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...
output:
51 203949 53 207948 54 211947 55 215946 56 219945 57 223944 58 227943 59 231942 60 235941 61 239940 62 243939 64 247938 65 251937 66 255936 67 259935 68 263934 69 267933 70 271932 71 275931 72 279930 73 283929 74 287928 75 291927 76 295926 77 299925 78 303924 79 307923 80 311922 81 315921 82 319920 ...