QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333105#7906. Almost ConvexlhzawaRE 0ms0kbC++141.8kb2024-02-19 17:15:522024-02-19 17:15:52

Judging History

你现在查看的是最新测评结果

  • [2024-02-19 17:15:52]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

6

result: