QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#602430#7906. Almost ConvexqzhfxTL 0ms4144kbC++233.1kb2024-10-01 00:56:382024-10-01 00:56:40

Judging History

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

  • [2024-10-01 00:56:40]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4144kb
  • [2024-10-01 00:56:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 7;
const int mod = 998244353;
const ll eps = 1e-7;

struct Point
{
    ll x, y;
    Point() {}
    Point(ll ax, ll ay)
    {
        x = ax, y = ay;
    }
    ll id(){
        return x * 2000000ll + y;
    }
    Point operator-(const Point &b) const
    {
        return Point(x - b.x, y - b.y);
    }
    bool operator<(const Point &b) const
    {
        if (x == b.x)
            return y < b.y;
        return x < b.x;
    }
    bool operator==(const Point &b) const
    {
        return ((x == b.x)) && ((y == b.y));
    }
};
ll cross(Point a, Point b)
{
    return a.x * b.y - a.y * b.x;
}
int lt(double x, double y)
{
    if (x > y)
        return 0;
    return 1;
}
Point O = {0, 0};
double theta(auto p) { return atan2(p.y, p.x); } // 求极角
void psort(vector<Point> &ps, Point c = O)       // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto p1, auto p2)
         { return lt(theta(p1 - c), theta(p2 - c)); });
}
std::vector<Point> getHull(std::vector<Point> p)
{
    std::vector<Point> h, l;
    std::sort(p.begin(), p.end(), [&](auto a, auto b)
              {
        if (a.x != b.x) {
            return a.x < b.x;
        } else {
            return a.y < b.y;
        } });
    p.erase(std::unique(p.begin(), p.end()), p.end());
    if (p.size() <= 1)
    {
        return p;
    }

    for (auto a : p)
    {
        while (h.size() > 1 && lt(cross(a - h.back(), a - h[h.size() - 2]), 0))
        {
            h.pop_back();
        }
        while (l.size() > 1 && lt(0, cross(a - l.back(), a - l[l.size() - 2])))
        {
            l.pop_back();
        }
        l.push_back(a);
        h.push_back(a);
    }

    l.pop_back();
    std::reverse(h.begin(), h.end());
    h.pop_back();
    l.insert(l.end(), h.begin(), h.end());
    return l;
}
void solve()
{
    int n;
    cin >> n;
    vector<Point> p;
    for (int i = 0; i < n; i++)
    {
        ll x, y;
        cin >> x >> y;
        p.push_back({x, y});
    }
    auto h = getHull(p);
    int ans = 1;
    map<Point, int> pm;
    for (auto x : h)
    {
        pm[x] = 1;
    }
    map<pair<ll, ll>, int> mp;
    for (int j = 1; j < h.size(); j++)
    {
        mp[{h[j - 1].id(), h[j].id()}] = 1;
        mp[{h[j].id(), h[j - 1].id()}] = 1;
    }
    mp[{h.back().id(), h[0].id()}] = mp[{h[0].id(), h.back().id()}] = 1;

    for (int i = 0; i < n; i++)
    {
        if (pm[p[i]])
            continue;
        vector<Point> v;
        for (int j = 0; j < n; j++)
        {
            if (i == j)
                continue;
            v.push_back(p[j]);
        }
        psort(v, p[i]);

        for (int j = 1; j < v.size(); j++)
        {

            if (mp[{v[j].id(), v[j - 1].id()}])
            {
                ans++;
            }
        }
        if (mp[{v.back().id(), v[0].id()}])
            ans++;
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 4144kb

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

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:


result: