QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#420429#7906. Almost ConvexSunlightZeroWA 0ms7692kbC++143.0kb2024-05-24 18:08:062024-05-24 18:08:06

Judging History

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

  • [2024-05-24 18:08:06]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7692kb
  • [2024-05-24 18:08:06]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr size_t MAXN = 1e5 + 5;

size_t n;

struct Point {
    ll x, y;

    friend Point operator-(Point u, Point v)
    {
        return {u.x - v.x, u.y - v.y};
    }

    friend bool operator==(Point u, Point v)
    {
        return u.x == v.x && u.y == v.y;
    }

    friend bool operator<(Point u, Point v)
    {
        return u.x < v.x || (u.x == v.x && u.y < v.y);
    }
} points[MAXN], convex[MAXN], inner[MAXN];

size_t n_cvx, n_inner;
set<Point> st;

bool cmp1(Point u, Point v)
{
    return u.x < v.x || (u.x == v.x && u.y > v.y);
}

ll cross(Point u, Point v)
{
    return u.x * v.y - u.y * v.x;
}

struct Cmp {
    Point o;
    bool operator()(Point u, Point v)
    {
        return cross(u - o, v - o) > 0;
    }
} cmp2;

size_t stk[MAXN], top;

ll dot(Point u, Point v)
{
    return u.x * v.x + u.y * v.y;
}

ll len2(Point u)
{
    return u.x * u.x + u.y * u.y;
}

int sgn(ll x)
{
    return x > 0 ? 1 : -1;
}

void andrew()
{
    sort(points + 1, points + n + 1, cmp1);
    
    top = 0;
    for (size_t i = 1; i <= n; i++)
    {
        while (top >= 2 && cross(points[stk[top]] - points[stk[top - 1]], 
            points[i] - points[stk[top]]) < 0)
        {
            top--;
        }
        stk[++top] = i;
    }
    for (size_t i = 1; i < top; i++)
    {
        convex[++n_cvx] = points[stk[i]];
        st.insert(points[stk[i]]);
    }
    top = 0;
    for (size_t i = n; i >= 1; i--)
    {
        while (top >= 2 && cross(points[stk[top]] - points[stk[top - 1]], 
            points[i] - points[stk[top]]) < 0)
        {
            top--;
        }
        stk[++top] = i;
    }
    for (size_t i = 1; i < top; i++)
    {
        convex[++n_cvx] = points[stk[i]];
        st.insert(points[stk[i]]);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (size_t i = 1; i <= n; i++)
    {
        cin >> points[i].x >> points[i].y;
    }
    andrew();
    ull ans = 1;
    for (size_t i = 1; i <= n; i++)
    {
        if (st.find(points[i]) == st.end())
        {
            inner[++n_inner] = points[i];
        }
    }
    for (size_t i = 1; i <= n_cvx; i++)
    {
        Point a = convex[i], b = convex[i % n_cvx + 1];
        cmp2.o = a;
        sort(inner + 1, inner + n_inner + 1, cmp2);
        bool has_u = false;
        Point u;
        for (size_t k = 1; k <= n_inner; k++)
        {
            Point p = inner[k];
            if (!has_u)
            {
                ans++;
                has_u = true;
                u = p;
                continue;
            }
            if (cross(p - b, u - b) > 0)
            {
                ans++;
                u = p;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 0ms
memory: 7692kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

6

result:

wrong answer 1st numbers differ - expected: '5', found: '6'