QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#622972 | #7906. Almost Convex | clouds_ | WA | 0ms | 32160kb | C++23 | 3.6kb | 2024-10-09 09:12:17 | 2024-10-09 09:12:17 |
Judging History
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'