QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#573401 | #7906. Almost Convex | rxzfn639 | TL | 1ms | 4228kb | C++23 | 3.9kb | 2024-09-18 18:34:56 | 2024-09-18 18:34:56 |
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 (n == 2000) cout << i << ' ' << o << '\n';
}
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: 3900kb
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: 4020kb
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: 3640kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4228kb
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: 3860kb
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:
0 3999 1 7998 2 11997 3 15996 4 19995 5 23994 6 27993 7 31992 8 35991 9 39990 10 43989 11 47988 13 51987 14 55986 15 59985 16 63984 17 67983 18 71982 19 75981 20 79980 21 83979 22 87978 23 91977 24 95976 25 99975 26 103974 27 107973 28 111972 29 115971 30 119970 31 123969 32 127968 33 131967 34 1359...