QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674399#7906. Almost ConvexTokaiZaopenWA 12ms4048kbC++203.0kb2024-10-25 15:34:272024-10-25 15:34:28

Judging History

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

  • [2024-10-25 15:34:28]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:4048kb
  • [2024-10-25 15:34:27]
  • 提交

answer

#include <bits/stdc++.h>

#define int ll
using ll = long long;

// #define MING_LE

const double eps = 1e-6;
const int inf = 1e18;

using namespace std;

struct point
{
    double x;
    double y;

    bool operator<(const point &o) const
    {
        if (abs(x - o.x) < eps)
            return y < o.y;
        return x < o.x;
    }

    double operator*(const point &o) const
    {
        return x * o.x + y * o.y;
    }

    point operator-(const point &o) const
    {
        return {x - o.x, y - o.y};
    }

    double cross(point o)
    {
        return x * o.y - y * o.x;
    }

    double dis(point o)
    {
        return sqrt((x - o.x) * (x - o.x) + (y - o.y) * (y - o.y));
    }
};

set<int> to[2010];

pair<vector<int>, int> GetCH(vector<point> &a, int len);
void solve();

signed main()
{
    // freopen("p2742.in", "r", stdin);

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int __ = 1;
    // cin >> __;

    while (__--)
        solve();

    return 0;
}

void solve()
{
    int n;
    cin >> n;
    vector<point> a(n + 5);
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;

    auto b = GetCH(a, n);
    b.first[b.second + 1] = b.first[1];
#ifdef MING_LE
    cout << b.second << "\n";
    for (int i = 1; i <= b.second; i++)
        cout << b.first[i] << " ";
    cout << '\n';
#endif
    vector<bool> vis(2010);
    for (int i = 1; i <= b.second; i++)
    {
        vis[b.first[i]] = 1;
    }

    int ans = 1;

    for (int i = 1; i <= b.second; i++)
    {
        auto u = a[b.first[i]], v = a[b.first[i + 1]];
        set<pair<double, double>> st;
        st.clear();
        double mn = inf;

        for (int j = 1; j <= n; j++)
        {
            if (vis[j])
                continue;

            double cl, cr;
            cl = (v - u) * (a[j] - u) / u.dis(v) / u.dis(a[j]);
            cr = (u - v) * (a[j] - v) / v.dis(u) / v.dis(a[j]);
            st.emplace(cl, cr);
        }
        for (auto it : st)
        {
            if (mn > it.second)
                ans++;
            mn = min(mn, it.second);
        }
    }

    cout << ans << '\n';
}

pair<vector<int>, int> GetCH(vector<point> &a, int len)
{
    vector<int> res(2 * len + 5);

    sort(a.begin() + 1, a.begin() + 1 + len);

    int tmp;
    int tot = 0;
    res[++tot] = 1;

    for (int i = 2; i <= len; i++)
    {
        while (tot >= 2 && (a[res[tot]] - a[res[tot - 1]]).cross(a[i] - a[res[tot]]) < 0)
            tot--;

        res[++tot] = i;
    }

    tmp = tot;

#ifdef MING_LE
    // cout << "/// " << tot << " ///\n";
    // for (int i = 1; i <= tot; i++)
    //     cout << res[i] << " ";
    // cout << '\n';
#endif

    for (int i = len - 1; i >= 1; i--)
    {
        while (tot > tmp && (a[res[tot]] - a[res[tot - 1]]).cross(a[i] - a[res[tot]]) < 0)
            tot--;

        res[++tot] = i;
    }

    return make_pair(res, tot - 1);
}

// g++ -o p2742.exe p2742.cpp && p2742.exe < P2742.in > output.txt

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4036kb

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: 3808kb

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: 3804kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 4048kb

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: 3812kb

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: 12ms
memory: 3992kb

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:

18950

result:

wrong answer 1st numbers differ - expected: '718', found: '18950'