QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710891 | #7906. Almost Convex | FUCKUCUP | WA | 7ms | 3852kb | C++20 | 2.3kb | 2024-11-04 22:50:40 | 2024-11-04 22:50:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int T, n, vis[maxn], stk[maxn], top;
struct point { int x, y; };
vector<point> p, convex;
inline point operator - (point p, point q) { return {p.x - q.x, p.y - q.y}; }
inline long long operator * (point p, point q) { return 1ll * p.x * q.y - 1ll * p.y * q.x; }
inline long long operator ^ (point p, point q) { return 1ll * p.x * q.x + 1ll * p.y * q.y; }
inline long long len2(point p) { return 1ll * p.x * p.x + 1ll * p.y * p.y; }
inline vector<point> calc_convex(vector<point> &p) {
vector<point> ans;
stk[top = 1] = 0;
for(int i = 1; i < p.size(); ++i) {
while(top > 1 && (p[stk[top]] - p[stk[top - 1]]) * (p[i] - p[stk[top]]) < 0) --top;
stk[++top] = i;
}
// for(int i = 1; i <= top; ++i) cout << p[stk[i]].x << ' ' << p[stk[i]].y << '\n';
int cur = top;
for(int i = (int)p.size() - 2; i >= 0; --i) {
while(top > cur && (p[stk[top]] - p[stk[top - 1]]) * (p[i] - p[stk[top]]) < 0) --top;
stk[++top] = i;
}
for(int i = 1; i <= top; ++i) ans.push_back(p[stk[i]]), vis[stk[i]] = 1;
// for(auto [x, y] : ans) cout << x << ',' << y << ' '; cout << "--\n";
return ans;
}
inline void solve() {
cin >> n, p = vector<point>(n);
for(int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
sort(p.begin(), p.end(), [&](auto p, auto q) { return p.x < q.x; });
for(int i = 0; i < n; ++i) vis[i] = 0;
convex = calc_convex(p);
// puts("s");
int ans = 1;
for(int i = 0; i < convex.size() - 1; ++i) {
vector<point> p2;
for(int j = 0; j < n; ++j) if(!vis[j]) p2.push_back(p[j]);
sort(p2.begin(), p2.end(), [&](auto a, auto b) {
long long l1 = len2(a - convex[i]), l2 = len2(b - convex[i]);
long long m1 = (convex[i + 1] - convex[i]) ^ (a - convex[i]);
long long m2 = (convex[i + 1] - convex[i]) ^ (b - convex[i]);
return (__int128)m1 * m1 * l2 > (__int128)m2 * m2 * l1;
});
// cout << convex[i].x << ',' << convex[i].y << ' ' << convex[i + 1].x << ',' << convex[i + 1].y << '\n';
// for(auto [x, y] : p2) cout << x << ',' << y << ' '; cout << '\n';
point mnp = convex[i + 1];
for(auto now : p2) if((mnp - convex[i + 1]) * (now - convex[i + 1]) >= 0) ++ans, mnp = now;
}
cout << ans << '\n';
}
int main() {
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
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: 3852kb
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: 3548kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3852kb
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: 3616kb
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: 7ms
memory: 3544kb
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:
150
result:
wrong answer 1st numbers differ - expected: '718', found: '150'