QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623014 | #7906. Almost Convex | clouds_ | WA | 3ms | 13008kb | C++23 | 2.4kb | 2024-10-09 09:35:21 | 2024-10-09 09:35:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define Vector Point
#define int long long
const double eps = 1e-8, pi = acos(-1);
const int N = 2e5 + 10;
struct Point
{
Point(int X = 0, int Y = 0) { x = X, y = Y; }
int x, y;
int fg;
} p[N], s[N];
Vector operator+(Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator-(Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator*(Vector a, double b) { return Vector(a.x * b, a.y * b); }
bool operator==(Vector a, Vector b) { return a.x == b.x && a.y == b.y; }
int dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
int cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
double Len(Vector a) { return sqrt(1.0 * dot(a, a)); }
Point O;
bool tbcmp(Point a, Point b)
{
if (cross(O - a, O - b) == 0)
return Len(O - a) < Len(O - b);
return cross(a - O, b - O) > 0;
}
vector<Point> ans2;
vector<Point> gettb(Point *p, int n)
{
for (int i = 1; i <= n; i++)
{
if (p[i].y < p[1].y || p[i].y == p[1].y && p[i].x < p[1].x)
swap(p[1], p[i]);
}
O = p[1];
sort(p + 2, p + n + 1, tbcmp);
vector<Point> ans;
ans.push_back(p[1]);
int idx = 0;
for (int i = 2; i <= n; i++)
{
while (idx >= 1 && cross(ans[idx] - ans[idx - 1], p[i] - ans[idx]) <= 0)
idx--, ans2.push_back(ans.back()), ans.pop_back();
idx++;
ans.push_back(p[i]);
}
return ans;
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i].x >> p[i].y;
vector<Point> ans1 = gettb(p, n);
int ans = 1;
for (auto i : ans2)
{
int num = 0;
for (auto j : ans1)
s[++num] = j, s[num].fg = 1;
for (auto j : ans2)
{
if (j.x == i.x && j.y == i.y)
continue;
s[++num] = j;
s[num].fg = 0;
}
O = i;
sort(s + 1, s + num + 1, tbcmp);
for (int j = 1; j <= num; j++)
{
Point p1 = s[j], p2 = s[j % num + 1];
if (p1.fg == 1 && p2.fg == 1)
ans++;
}
}
cout << ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(1);
int t = 1;
while (t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 13008kb
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'