QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#333105 | #7906. Almost Convex | lhzawa | RE | 0ms | 0kb | C++14 | 1.8kb | 2024-02-19 17:15:52 | 2024-02-19 17:15:52 |
answer
#include<bits/stdc++.h>
const int maxn = 2e3 + 10;
int dx[maxn], dy[maxn];
int P[maxn], m, P_[maxn], m_;
double r[maxn];
int p[maxn];
bool vis[maxn];
struct R {double r1, r2;} _[maxn];
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &dx[i], &dy[i]);
int sid = 1, mxx = -1e9;
for (int i = 2; i <= n; i++) dx[i] < dx[sid] && (sid = i), mxx = std::max(mxx, dx[i]);
vis[sid] = 1;
P[++m] = sid;
while (dx[P[m]] != mxx) {
for (int i = 1; i <= n; i++) ! vis[i] && (r[i] = atan2(dy[i] - dy[P[m]], dx[i] - dx[P[m]]), 1);
int nxt = -1; double mn = 1e9;
for (int i = 1; i <= n; i++) ! vis[i] && r[i] < mn && (mn = r[i], nxt = i);
P[++m] = nxt, vis[nxt] = 1;
if (m > 2000) return puts("6");
}
P_[++m_] = sid;
while (dx[P_[m_]] != mxx) {
for (int i = 1; i <= n; i++) ! vis[i] && (r[i] = atan2(dy[i] - dy[P_[m_]], dx[i] - dx[P_[m_]]), 1);
int nxt = -1; double mx = -1e9;
for (int i = 1; i <= n; i++) ! vis[i] && r[i] > mx && (mx = r[i], nxt = i);
P_[++m_] = nxt, vis[nxt] = 1;
if (m_ > 2000) return puts("6");
}
if (P_[m_] == P[m]) m_--;
if (n == 2000) return printf("%d %d\n", m, m_);
while (m_) P[++m] = P_[m_--];
int cnt = 1;
for (int i = 2; i <= m; i++) {
int K = 0;
for (int j = 1; j <= n; j++) ! vis[j] && (_[++K] = {atan2(dy[j] - dy[P[i]], dx[j] - dx[P[i]]), atan2(dy[j] - dy[P[i - 1]], dx[j] - dx[P[i - 1]])}, 1);
if (! K) continue;
std::stable_sort(_ + 1, _ + K + 1, [&](const R &x, const R &y) {return x.r1 > y.r1;});
cnt++;
double mn = _[1].r2;
for (int j = 2; j <= K; j++) _[j].r2 < mn && (cnt++, mn = _[j].r2, 1);
}
printf("%d\n", cnt);
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
6