QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#573416 | #7906. Almost Convex | rxzfn639 | TL | 1ms | 4080kb | C++23 | 3.9kb | 2024-09-18 18:39:11 | 2024-09-18 18:39:12 |
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 > 2000000 && 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: 1ms
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: 3900kb
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: 3784kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4080kb
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: 3724kb
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:
511 2003499 512 2007498 513 2011497 514 2015496 515 2019495 516 2023494 517 2027493 518 2031492 519 2035491 520 2039490 521 2043489 522 2047488 523 2051487 524 2055486 525 2059485 526 2063484 527 2067483 528 2071482 529 2075481 530 2079480 532 2083479 533 2087478 534 2091477 535 2095476 536 2099475 ...