QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#298894#7906. Almost Convexucup-team203#WA 0ms3784kbC++204.5kb2024-01-06 15:42:112024-01-06 15:42:11

Judging History

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

  • [2024-01-06 15:42:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3784kb
  • [2024-01-06 15:42:11]
  • 提交

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; }
    long double dis(Point tmp)
    {
        long double len = sqrtl(x * x + y * y);
        return 1.0 * abs(y * (tmp.x - x) + x * (tmp.y - 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;
        vector<int> vis(n + 1);
        vis[p] = 1;
        for (int j = p + 1, lst = p;; lst++, j++)
        {
            if (j == top2)
                j = 1;
            if (lst == top2)
                lst = 1;
            if (vis[j])
                break;
            if ((num[Conv2[lst]] - num[cur]).cross(num[Conv2[j]] - num[Conv2[lst]]) <= 0)
            {
                vis[j] = 1;
                ans++;
            }
            else
                break;
        }
        for (int j = p - 1, lst = p;; lst--, j--)
        {
            if (!j)
                j = top2 - 1;
            if (!lst)
                lst - top2 - 1;
            if (vis[j])
                break;
            if ((num[Conv2[lst]] - num[nxt]).cross(num[Conv2[j]] - num[Conv2[lst]]) >= 0)
            {
                vis[j] = 1;
                ans++;
            }
            else
                break;
        }
    }
    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: 3512kb

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3500kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

8

result:

wrong answer 1st numbers differ - expected: '7', found: '8'