QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276643 | #7906. Almost Convex | therehello | WA | 114ms | 4140kb | C++20 | 8.9kb | 2023-12-06 02:02:54 | 2023-12-06 02:02:55 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef DEBUG
#include <debug.cpp>
#else
#define debug(...)
#endif
using namespace std;
using ll = long long;
using lf = long double;
constexpr double inf = 1e100;
// 向量
struct vec {
static bool cmp(const vec &a, const vec &b) { return tie(a.x, a.y) < tie(b.x, b.y); }
ll x, y;
vec() : x(0), y(0) {}
vec(ll _x, ll _y) : x(_x), y(_y) {}
vec rotleft() const { return {-y, x}; }
vec rotright() const { return {y, -x}; }
// 模
ll len2() const { return x * x + y * y; }
double len() const { return sqrt(x * x + y * y); }
// 是否在上半轴
bool up() const { return y > 0 || y == 0 && x >= 0; }
bool operator==(const vec &b) const { return tie(x, y) == tie(b.x, b.y); }
// 极角排序
bool operator<(const vec &b) const {
return cmp(*this, b);
if (up() != b.up()) return up() > b.up();
ll tmp = (*this) ^ b;
return tmp ? tmp > 0 : cmp(*this, b);
}
vec operator+(const vec &b) const { return {x + b.x, y + b.y}; }
vec operator-() const { return {-x, -y}; }
vec operator-(const vec &b) const { return -b + (*this); }
vec operator*(ll b) const { return {x * b, y * b}; }
ll operator*(const vec &b) const { return x * b.x + y * b.y; }
// 叉积 结果大于0,a到b为逆时针,小于0,a到b顺时针,
// 等于0共线,可能同向或反向,结果绝对值表示 a b 形成的平行四边行的面积
ll operator^(const vec &b) const { return x * b.y - y * b.x; }
friend istream &operator>>(istream &in, vec &data) {
in >> data.x >> data.y;
return in;
}
friend ostream &operator<<(ostream &out, const vec &data) {
out << data.x << " " << data.y;
return out;
}
};
lf angle(const vec &a, const vec &b) { return atan2(abs(a ^ b), a * b); }
ll cross(const vec &a, const vec &b, const vec &c) { return (a - c) ^ (b - c); }
// 多边形的面积a
double polygon_area(vector<vec> &p) {
ll area = 0;
for (int i = 1; i < p.size(); i++) area += p[i - 1] ^ p[i];
area += p.back() ^ p[0];
return abs(area / 2.0);
}
// 多边形的周长
double polygon_len(vector<vec> &p) {
double len = 0;
for (int i = 1; i < p.size(); i++) len += (p[i - 1] - p[i]).len();
len += (p.back() - p[0]).len();
return len;
}
// 以整点为顶点的线段上的整点个数
ll count(const vec &a, const vec &b) {
vec c = a - b;
return gcd(abs(c.x), abs(c.y)) + 1;
}
// 以整点为顶点的多边形边上整点个数
ll count(vector<vec> &p) {
ll cnt = 0;
for (int i = 1; i < p.size(); i++) cnt += count(p[i - 1], p[i]);
cnt += count(p.back(), p[0]);
return cnt - p.size();
}
// 判断点是否在凸包内,凸包必须为逆时针顺序
bool in_polygon(const vec &a, vector<vec> &p) {
int n = p.size();
if (n == 0) return 0;
if (n == 1) return a == p[0];
if (n == 2) return cross(a, p[1], p[0]) == 0 && (p[0] - a) * (p[1] - a) <= 0;
if (cross(a, p[1], p[0]) > 0 || cross(p.back(), a, p[0]) > 0) return 0;
auto cmp = [&](vec &x, const vec &y) { return ((x - p[0]) ^ y) >= 0; };
int i = lower_bound(p.begin() + 2, p.end() - 1, a - p[0], cmp) - p.begin() - 1;
return cross(p[(i + 1) % n], a, p[i]) >= 0;
}
// 凸包直径的两个端点
auto polygon_dia(vector<vec> &p) {
int n = p.size();
array<vec, 2> res{};
if (n == 1) return res;
if (n == 2) return res = {p[0], p[1]};
ll mx = 0;
for (int i = 0, j = 2; i < n; i++) {
while (abs(cross(p[i], p[(i + 1) % n], p[j])) <=
abs(cross(p[i], p[(i + 1) % n], p[(j + 1) % n])))
j = (j + 1) % n;
ll tmp = (p[i] - p[j]).len2();
if (tmp > mx) {
mx = tmp;
res = {p[i], p[j]};
}
tmp = (p[(i + 1) % n] - p[j]).len2();
if (tmp > mx) {
mx = tmp;
res = {p[(i + 1) % n], p[j]};
}
}
return res;
}
// 凸包
auto convex_hull(vector<vec> &p) {
sort(p.begin(), p.end(), vec::cmp);
int n = p.size();
vector sta(n + 1, 0);
vector v(n, false);
int tp = -1;
sta[++tp] = 0;
auto update = [&](int lim, int i) {
while (tp > lim && cross(p[i], p[sta[tp]], p[sta[tp - 1]]) >= 0) v[sta[tp--]] = 0;
sta[++tp] = i;
v[i] = 1;
};
for (int i = 1; i < n; i++) update(0, i);
int cnt = tp;
for (int i = n - 1; i >= 0; i--) {
if (v[i]) continue;
update(cnt, i);
}
vector<vec> res(tp);
for (int i = 0; i < tp; i++) res[i] = p[sta[i]];
return res;
}
// 闵可夫斯基和,两个点集的和构成一个凸包
auto minkowski(vector<vec> &a, vector<vec> &b) {
rotate(a.begin(), min_element(a.begin(), a.end(), vec::cmp), a.end());
rotate(b.begin(), min_element(b.begin(), b.end(), vec::cmp), b.end());
int n = a.size(), m = b.size();
vector<vec> c{a[0] + b[0]};
c.reserve(n + m);
int i = 0, j = 0;
while (i < n && j < m) {
vec x = a[(i + 1) % n] - a[i];
vec y = b[(j + 1) % m] - b[j];
c.push_back(c.back() + ((x ^ y) >= 0 ? (i++, x) : (j++, y)));
}
while (i + 1 < n) {
c.push_back(c.back() + a[(i + 1) % n] - a[i]);
i++;
}
while (j + 1 < m) {
c.push_back(c.back() + b[(j + 1) % m] - b[j]);
j++;
}
return c;
}
// 过凸多边形外一点求凸多边形的切线,返回切点下标
auto tangent(const vec &a, vector<vec> &p) {
int n = p.size();
int l = -1, r = -1;
for (int i = 0; i < n; i++) {
ll tmp1 = cross(p[i], p[(i - 1 + n) % n], a);
ll tmp2 = cross(p[i], p[(i + 1) % n], a);
if (l == -1 && tmp1 <= 0 && tmp2 <= 0) l = i;
else if (r == -1 && tmp1 >= 0 && tmp2 >= 0) r = i;
}
return array{l, r};
}
// 直线
struct line {
vec p, d;
line() {}
line(const vec &a, const vec &b) : p(a), d(b - a) {}
};
// 点到直线距离
double dis(const vec &a, const line &b) { return abs((b.p - a) ^ (b.p + b.d - a)) / b.d.len(); }
// 点在直线哪边,大于0在左边,等于0在线上,小于0在右边
ll side_line(const vec &a, const line &b) { return b.d ^ (a - b.p); }
// 两直线是否垂直
bool perpen(const line &a, const line &b) { return a.d * b.d == 0; }
// 两直线是否平行
bool parallel(const line &a, const line &b) { return (a.d ^ b.d) == 0; }
// 点的垂线是否与线段有交点
bool perpen(const vec &a, const line &b) {
vec p(-b.d.y, b.d.x);
bool cross1 = (p ^ (b.p - a)) > 0;
bool cross2 = (p ^ (b.p + b.d - a)) > 0;
return cross1 != cross2;
}
// 点到线段距离
double dis_seg(const vec &a, const line &b) {
if (perpen(a, b)) return dis(a, b);
return min((b.p - a).len(), (b.p + b.d - a).len());
}
// 点到凸包距离
double dis(const vec &a, vector<vec> &p) {
double res = inf;
for (int i = 1; i < p.size(); i++) res = min(dis_seg(a, line(p[i - 1], p[i])), res);
res = min(dis_seg(a, line(p.back(), p[0] - p.back())), res);
return res;
}
// 两直线交点
vec intersection(ll A, ll B, ll C, ll D, ll E, ll F) {
return {(B * F - C * E) / (A * E - B * D), (C * D - A * F) / (A * E - B * D)};
}
// 两直线交点
vec intersection(const line &a, const line &b) {
return intersection(a.d.y, -a.d.x, a.d.x * a.p.y - a.d.y * a.p.x, b.d.y, -b.d.x,
b.d.x * b.p.y - b.d.y * b.p.x);
}
void solve() {
int n;
cin >> n;
vector<vec> p(n);
for (auto &i : p) cin >> i;
auto convex = convex_hull(p);
debug(convex);
set<vec> S(convex.begin(), convex.end());
convex.push_back(convex[0]);
vector<vec> p2;
for (auto &i : p) {
if (S.count(i)) continue;
p2.push_back(i);
}
int ans = 1;
for (auto &o : p2) {
vector<vec> p3;
for (auto &i : p2) {
if (o == i) continue;
p3.push_back(i - o);
}
lf mn = 1e100;
int pos = 0;
for (auto &i : p3) {
lf tmp = angle(convex[0] - o, i);
if (tmp < mn) {
mn = tmp;
pos = &i - &p3[0];
}
}
rotate(p3.begin(), p3.begin() + pos, p3.end());
for (int i = 1, j = 0; i < convex.size(); i++) {
bool ok = 1;
while (j < p3.size() && ((convex[i - 1] - o) ^ p3[j]) >= 0 &&
(p3[j] ^ (convex[i] - o)) >= 0) {
if (((convex[i - 1] - o) ^ p3[j]) > 0 && (p3[j] ^ (convex[i] - o)) > 0) ok = 0;
j++;
}
debug(o, i, ok);
ans += ok;
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3972kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4140kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 114ms
memory: 4076kb
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...
output:
80620
result:
wrong answer 1st numbers differ - expected: '718', found: '80620'