QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#627817 | #7906. Almost Convex | hhhhyf | WA | 265ms | 3772kb | C++20 | 2.5kb | 2024-10-10 17:15:56 | 2024-10-10 17:15:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
void print() { cout << '\n'; }
template <typename T, typename...Args>
void print(T t, Args...args) { cout << t << ' '; print(args...); }
using ll = long long;
const int N = 50005;
using T = ll;
const T pi = acos(-1);
using Point = array<T, 2>;
Point operator - (const Point a, const Point b) {
auto [x1, y1] = a;
auto [x2, y2] = b;
return {x1 - x2, y1 - y2};
}
T cross (Point a, Point b) {
auto [x1, y1] = a;
auto [x2, y2] = b;
return x1 * y2 - x2 * y1;
}
T dis (Point& a, Point& b) {
return sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));
}
vector<int> get_convex_hull (vector<Point> p) {
int n = p.size();
vector<int> stk(n + 1);
int top = -1;
for (int i = 0; i < n; i ++) {
while (top >= 1 && cross(p[stk[top]] - p[stk[top - 1]], p[i] - p[stk[top - 1]]) <= 0) {
top --;
}
stk[++ top] = i;
}
int t = top;
for (int i = n - 2; i >= 0; i --) {
while (top > t && cross(p[stk[top]] - p[stk[top - 1]], p[i] - p[stk[top - 1]]) <= 0) {
top --;
}
stk[++ top] = i;
}
stk.resize(top + 1);
return stk;
}
int sign (Point p) {
auto [x, y] = p;
return x > 0 || x == 0 && y > 0;
}
void solve () {
int n;
cin >> n;
vector<Point> a(n);
for (auto& [x, y]: a) {
cin >> x >> y;
}
sort(all(a));
auto convex = get_convex_hull(a);
vector<int> on_convex(n);
for (auto& i: convex) {
on_convex[i] = 1;
}
int ans = 1;
for (int i = 0; i < n; i ++) {
if (!on_convex[i]) {
vector<int> p;
for (int j = 0; j < n; j ++) {
if (j != i) {
p.push_back(j);
}
}
sort(all(p),
[&](int x, int y) {
if (sign(a[x]) != sign(a[y])) {
return sign(a[x]) < sign(a[y]);
}
return cross(a[x] - a[i], a[y] - a[i]) > 0;
});
int m = p.size();
for (int x = 0; x < m; x ++) {
ans += on_convex[p[x]] && on_convex[p[(x + 1) % m]];
}
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t --) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3612kb
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: 3532kb
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: 3772kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3492kb
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: 1ms
memory: 3772kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 265ms
memory: 3708kb
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:
846
result:
wrong answer 1st numbers differ - expected: '718', found: '846'