QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#622972#7906. Almost Convexclouds_WA 0ms32160kbC++233.6kb2024-10-09 09:12:172024-10-09 09:12:17

Judging History

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

  • [2024-10-09 09:12:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:32160kb
  • [2024-10-09 09:12:17]
  • 提交

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;

struct node
{
    pii x;
    int  op;
} q[N];

/*
double check(pii a1, pii a2, pii b1, pii b2) // 叉积大于零左转,小于右转·
{
    return (a2.x - a1.x) * (b2.y - b1.y) - (b2.x - b1.x) * (a2.y - a1.y);
}

double dis(pii a, pii b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

bool cmp(node aa, node bb) // 极角排序
{
    pii a = aa.x;
    pii b = bb.x;
    double now = check(q[0].x, a, q[0].x, b);
    if (now > 0)
        return 1;
    if (now == 0 && dis(q[0].x, a) < dis(q[0].x, b))
        return 1;
    return 0;
}*/

int dot(pii a, pii b)
{
    return a.x * b.x + a.y * b.y;
}

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

double Len(pii a)
{
    return sqrt(1.0 * dot(a, a));
}

bool cmp(node aa, node bb) // 极角排序
{
    pii a = aa.x;
    pii b = bb.x;
    if(cross(O-a,O-b)==0)
        return Len(O - a) < Len(O - b);
    return cross(a - O, b - O) > 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++)
    {
        int sum = 0;
        for (int l = 0; l < v.size(); l++)
        {
            if (l != i)
            {
                q[++sum] = {v[l], 0};
            }
        }
        for (int l = 0; l < n; l++)
            q[++sum] = {a[l], 1};
        O = v[i];
        sort(q+1, q+1+sum, cmp);
        // cout << O.x << " " << O.y << endl;
        for (int l = 1; l <= sum; l++)
        {
            // cout << q[l].x.x << " " << q[l].x.y << endl;
            int t1 = q[l].op, t2 = q[l % sum+1].op;
            if (t1==1 && t2==1)
                ans++;
        }
        // cout << ans << endl;
    }
    cout << ans << endl;
}
signed main()
{
    ios;
    int T = 1;
    for (int i = 1; i <= T; i++)
    {
        // cout << "Case " << i << ": ";
        solve();
    }

    return 0;
}

详细

Test #1:

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

input:

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

output:

8

result:

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