QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#420390#7906. Almost ConvexSunlightZeroWA 5ms7856kbC++143.3kb2024-05-24 17:02:242024-05-24 17:02:25

Judging History

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

  • [2024-05-24 17:02:25]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:7856kb
  • [2024-05-24 17:02:24]
  • 提交

answer

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

using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
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;

i128 sqr(ll x)
{
    return (i128) x * x;
}

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);
        ll cos_up = -1;
        i128 cos_down = 1;
        for (size_t k = 1; k <= n_inner; k++)
        {
            Point p = inner[k];
            ll dot_prod = dot(a - b, p - b);
            ll norm1 = len2(a - b), norm2 = len2(p - b);
            if (sgn(dot_prod) > sgn(cos_up) ||
                sgn(dot_prod) == 1 && sgn(cos_up) == 1 &&
                sqr(dot_prod) * cos_down > sqr(cos_up) * norm1 * norm2 ||
                sgn(dot_prod) == -1 && sgn(cos_up) == -1 &&
                sqr(dot_prod) * cos_down < sqr(cos_up) * norm1 * norm2
            )
            {
                ans++;
                cos_up = dot_prod;
                cos_down = norm1 * norm2;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7740kb

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: 1ms
memory: 7628kb

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: 1ms
memory: 7696kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: 5ms
memory: 7856kb

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:

23863

result:

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