QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#694672 | #7906. Almost Convex | ljljljlj | RE | 0ms | 0kb | C++20 | 2.5kb | 2024-10-31 18:26:39 | 2024-10-31 18:26:40 |
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