QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#332948#7906. Almost ConvexlhzawaCompile Error//C++141.6kb2024-02-19 16:37:122024-02-19 16:37:12

Judging History

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

  • [2024-02-19 16:37:12]
  • 评测
  • [2024-02-19 16:37:12]
  • 提交

answer

#include<bits/stdc++.h>
const int maxn = 2e4 + 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]);
    P[++m] = sid;
    while (dx[P[m]] != mxx) {
        for (int i = 1; i <= n; i++) r[i] = atan2(dy[i] - dy[P[m]], dx[i] - dx[P[m]]);
        int nxt = P[m] == 1 ? 2 : 1;
        for (int i = 1; i <= n; i++) i != P[m] && r[i] < r[nxt] && (nxt = i);
        P[++m] = nxt;
    }
    P_[++m_] = sid;
    while (dx[P_[m_]] != mxx) {
        for (int i = 1; i <= n; i++) r[i] = atan2(dy[i] - dy[P_[m_]], dx[i] - dx[P_[m_]]);
        int nxt = P_[m_] == 1 ? 2 : 1;
        for (int i = 1; i <= n; i++) i != P_[m_] && r[i] > r[nxt] && (nxt = i);
        P_[++m_] = nxt;
    }
    if (P_[m_] == P[m]) m_--;
    while (m_) P[++m] = P_[m_--];
    for (int i = 1; i <= m; i++) vis[P[i]] = 1; 
    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::static_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

answer.code: In function ‘int main()’:
answer.code:36:14: error: ‘static_sort’ is not a member of ‘std’; did you mean ‘stable_sort’?
   36 |         std::static_sort(_ + 1, _ + K + 1, [&](const R &x, const R &y) {return x.r1 > y.r1;});
      |              ^~~~~~~~~~~
      |              stable_sort
answer.code:10:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   10 |     int n; scanf("%d", &n);
      |            ~~~~~^~~~~~~~~~
answer.code:11:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   11 |     for (int i = 1; i <= n; i++) scanf("%d%d", &dx[i], &dy[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~