QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694672#7906. Almost ConvexljljljljRE 0ms0kbC++202.5kb2024-10-31 18:26:392024-10-31 18:26:40

Judging History

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

  • [2024-10-31 18:26:40]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-31 18:26:39]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Point
{
    int x, y;
};
using vec = Point;
using Points = vector<Point>;
const double eps = 1e-9;
Point o = {0, 0};
Points a;
bool lt(double x, double y)
{
    return x - y < -eps;
}
vec operator-(vec u, vec v)
{
    return {u.x - v.x, u.y - v.y};
}
int operator^(vec u, vec v)
{
    return u.x * v.y - u.y * v.x;
}
double len(vec v, vec u)
{
    return sqrt((v.x - u.x) * (v.x - u.x) + (v.y - u.y) * (v.y - u.y));
}
int qu(Point p)
{
    return lt(p.y, 0) << 1 | lt(p.x, 0) ^ lt(p.y, 0);
}
bool check(Point p, Point q, Point r)
{
    return lt((q - p) ^ (r - q), 0);
}
signed main()
{
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        a.push_back({x, y});
    }
    sort(a.begin(), a.end(), [&](auto v1, auto v2)
         {
        if(v1.x==v2.x)
        return v1.y<v2.y;
        else
        return v1.x<v2.x; });
    vector<int> st, used(n + 1, 0);
    st.push_back(0);
    for (int i = 1; i < a.size(); i++)
    {
        while (st.size() > 1 && check(a[st[st.size() - 2]], a[st.back()], a[i]))
            used[st.back()] = 0, st.pop_back();
        st.push_back(i);
        used[i] = 1;
    }
    for (int i = a.size() - 2; i >= 0; i--)
    {
        if (used[i])
            continue;
        while (st.size() > 1 && check(a[st[st.size() - 2]], a[st.back()], a[i]))
            st.pop_back();
        st.push_back(i);
    }
    for (auto x : st)
    {
        used[x] = 1;
       // cout << a[x].x << ' ' << a[x].y << endl;
    }
    st.pop_back();
    ans = st.size() * (n - st.size());
    for (int i = 0; i < n; i++)
    {
        if (used[i])
            continue;
        vector<double> jijiao;
        vector<int> vis(st.size() + 1, 0);
        for (int j = 0; j < st.size(); j++)
        {
            jijiao.push_back(atan2((a[st[j]] - a[i]).y, (a[st[j]] - a[i]).x));
        }
        jijiao.push_back(1e10);
        sort(jijiao.begin(), jijiao.end());
        for (int j = 0; j < n; j++)
        {
            if (i == j || used[j])
                continue;
            int it = lower_bound(jijiao.begin(), jijiao.end(), atan2((a[j] - a[i]).y, (a[j] - a[i]).x)) - jijiao.begin();
            vis[it % st.size()] = 1;
        }
        for (int j = 0; j < st.size(); j++)
        {
            if (vis[j] == 1)
                ans--;
        }
    }
    cout << ans + 1;
    system("pause");
}

详细

Test #1:

score: 0
Dangerous Syscalls

input:

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

output:


result: