QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#298879#7906. Almost Convexucup-team203#WA 1ms3604kbC++204.0kb2024-01-06 15:32:052024-01-06 15:32:06

Judging History

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

  • [2024-01-06 15:32:06]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3604kb
  • [2024-01-06 15:32:05]
  • 提交

answer

#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
const int N = 2e3 + 5;
// const int B = 340;
// const int M = 5e3 + 5;
// const int base = 1753591;
// const int mod = 998244353;
// const int mod = 1e9 + 7;
// const double pi = acos(-1);

struct Point
{
    i64 x, y;
    bool operator<(const Point &tmp) const
    {
        if (x == tmp.x)
            return y < tmp.y;
        return x < tmp.x;
    }
    Point operator-(Point tmp)
    {
        Point res;
        res.x = x - tmp.x;
        res.y = y - tmp.y;
        return res;
    }
    i64 cross(Point tmp) { return x * tmp.y - y * tmp.x; }
    i64 dis2(Point tmp) { return (x - tmp.x) * (x - tmp.x) + (y - tmp.y) * (y - tmp.y); }
    long double dis(Point tmp)
    {
        long double len = sqrtl(dis2(Point{0, 0}));
        return 1.0 * (y * tmp.x + x * tmp.y) / len;
    }
} num[N];
int n, vis1[N], vis2[N], Conv1[N], Conv2[N], top1, top2;
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> num[i].x >> num[i].y;
    sort(num + 1, num + n + 1);
    []()
    {
        Conv1[top1 = 1] = 1;
        stack<int> stk;
        stk.push(1);
        for (int i = 2; i <= n; i++)
        {
            while (top1 > 1 && (num[Conv1[top1]] - num[Conv1[top1 - 1]]).cross(num[i] - num[Conv1[top1]]) >= 0)
            {
                vis1[stk.top()] = 0;
                stk.pop();
                top1--;
            }
            vis1[i] = 1;
            stk.push(i);
            Conv1[++top1] = i;
        }
        int h = top1;
        for (int i = n - 1; i >= 1; i--)
        {
            if (vis1[i])
                continue;
            while (top1 > h && (num[Conv1[top1]] - num[Conv1[top1 - 1]]).cross(num[i] - num[Conv1[top1]]) >= 0)
            {
                vis1[stk.top()] = 0;
                stk.pop();
                top1--;
            }
            vis1[i] = 1;
            stk.push(i);
            Conv1[++top1] = i;
        }
    }();
    []()
    {
        stack<int> stk;
        int p = 0;
        for (int i = n; i >= 1; i--)
            if (!vis1[i])
                p = i;
        if (!p)
            return;
        stk.push(p);
        Conv2[top2 = 1] = p;
        for (int i = 2; i <= n; i++)
        {
            if (vis1[i])
                continue;
            while (top2 > 1 && (num[Conv2[top2]] - num[Conv2[top2 - 1]]).cross(num[i] - num[Conv2[top2]]) >= 0)
            {
                vis2[stk.top()] = 0;
                stk.pop();
                top2--;
            }
            vis2[i] = 1;
            stk.push(i);
            Conv2[++top2] = i;
        }
        int h = top2;
        for (int i = n - 1; i >= 1; i--)
        {
            if (vis2[i] || vis1[i])
                continue;
            while (top2 > h && (num[Conv2[top2]] - num[Conv2[top2 - 1]]).cross(num[i] - num[Conv2[top2]]) >= 0)
            {
                vis2[stk.top()] = 0;
                stk.pop();
                top2--;
            }
            vis2[i] = 1;
            stk.push(i);
            Conv2[++top2] = i;
        }
    }();
    int ans = 1;
    for (int i = 1; i < top1 && top2; i++)
    {
        int cur = Conv1[i], nxt = Conv1[i + 1];
        ans++;
        int p = 1;
        for (int j = 2; j < top2; j++)
            if ((num[nxt] - num[cur]).dis(num[Conv2[j]]) < (num[nxt] - num[cur]).dis(num[Conv2[p]]))
                p = j;
        for (int j = 1; j < top2; j++)
        {
            if (j == p)
                continue;
            Point tmp = num[Conv2[j]] - num[Conv2[p]];
            i64 c1 = tmp.cross(num[Conv2[j]] - num[cur]);
            i64 c2 = tmp.cross(num[Conv2[j]] - num[nxt]);
            if ((__int128_t)c1 * c2 > 0)
                ans++;
        }
    }
    cout << ans << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    cout << fixed << setprecision(10);
    while (t--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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

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:

1607

result:

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