QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622936#7906. Almost Convexclouds_WA 0ms7664kbC++233.4kb2024-10-09 08:37:322024-10-09 08:37:32

Judging History

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

  • [2024-10-09 08:37:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7664kb
  • [2024-10-09 08:37:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false), cin.tie(nullptr)
#define int long long
#define ll long long
#define endl "\n"
#define x first
#define y second
#define pi acos(-1)
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
const int eps = 1e-6;
const int N = 1e6 + 10, M = 1010, INF = 0x3f3f3f3f;
const int mod = 998244353;
pii a[N];
pii p[N];
int n, top, stk[N];
bool used[N];
vector<pii> v;
pii operator-(pii a, pii b)
{
    return {a.x - b.x, a.y - b.y};
}

int operator*(pii a, pii b)
{
    return a.x * b.y - a.y * b.x;
}

int area(pii a, pii b, pii c)
{
    return (b - a) * (c - a); // 向量的叉积
}

int lens(pii a, pii b) // 两点间距离
{
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return dx * dx + dy * dy;
}
void andrew()
{
    sort(p, p + n);
    for (int i = 0; i < n; i++)
    {
        while (top >= 2 && area(p[stk[top - 2]], p[stk[top - 1]], p[i]) <= 0)
        {
            if (area(p[stk[top - 2]], p[stk[top - 1]], p[i]) < 0)
                used[stk[top - 1]] = 0;
            top--;
        }
        stk[top++] = i;
        used[i] = 1;
    }
    used[0] = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        if (used[i])
            continue;
        while (top >= 2 && area(p[stk[top - 2]], p[stk[top - 1]], p[i]) <= 0)
        {
            top--;
            v.push_back(p[stk[top]]); // 非凸包的点
        }
        stk[top++] = i;
    }
    top--;
}
pii O;

int cross(int x1, int y1, int x2, int y2)
{
    return (x1 * y2 - x2 * y1);
}
int compare(pii a, pii b, pii c) // 计算极角
{
    return cross((b.x - a.x), (b.y - a.y), (c.x - a.x), (c.y - a.y));
}

int cmp2(piii a, piii b)
{
    pii c = O;                     // 原点
    if (compare(c, a.x, b.x) == 0) // 计算叉积,函数在上面有介绍,如果叉积相等,按照X从小到大排序
        return a.x.x < b.x.x;
    else
        return compare(c, a.x, b.x) > 0;
}

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> p[i].x >> p[i].y;
        used[i] = 0;
    }
    used[n] = 0;
    andrew();
    for (int i = 0; i < top; i++)
        a[i] = p[stk[i]];
    n = top;
    int ans = 0;

    for (int i = 0; i < v.size(); i++)
    {
        O = v[i];
        vector<piii> q;
        q.push_back({v[i], 0});
        for (int l = 0; l < n; l++)
            q.push_back({a[l], 1});
        for (int l = 0; l < v.size(); l++)
        {
            if (l != i)
            {
                q.push_back({v[l], 0});
            }
        }
        sort(q.begin(), q.end(), cmp2);
        vector<bool> pp;
        for (int l = 0; l < q.size(); l++)
        {
            if (q[l].x == O)
                continue;
            pp.push_back(q[l].y);
        }
        // if (pp.size())
        //     pp.push_back(pp[0]);
        for (int l = 0; l < pp.size() - 1; l++)
        {
            if (pp[l] && pp[l + 1])
                ans++;
        }
        if(pp.size()>=2)
        {
            if(pp[pp.size()-1]&&pp[0])
                ans++;
        }
        // cout << ans << endl;
    }
    cout << ans + 1 << endl;
}
signed main()
{
    ios;
    int T = 1;
    for (int i = 1; i <= T; i++)
    {
        // cout << "Case " << i << ": ";
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7664kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

10

result:

wrong answer 1st numbers differ - expected: '9', found: '10'