QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293082 | #7906. Almost Convex | Sy03 | TL | 1ms | 4100kb | C++20 | 15.5kb | 2023-12-28 21:30:17 | 2023-12-28 21:30:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;
using ull = unsigned long long;
using ll = long long;
#define endl '\n'
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int maxn = 2e5 + 10;
const int mod = 1000000007;
#define inl inline
#define fr(i, a, b) for (int i = a; i <= b; i++)
#define ford(i, a, b) for (int i = a; i >= b; i--)
#define forall(i, a) for (auto &i : a)
/**
____ ___ _____
/ ___| _ _ / _ \___ /
\___ \| | | | | | ||_ \
___) | |_| | |_| |__) |
|____/ \__, |\___/____/
|___/
*/
istream &operator>>(istream &in, vector<int> &v)
{
for (auto &i : v)
in >> i;
return in;
}
ostream &operator<<(ostream &out, vector<int> &v)
{
for (auto &i : v)
out << i << " ";
return out;
}
bool _output = 0;
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db EPS = 1e-9;
inline int sign(db a)
{
return a < -EPS ? -1 : a > EPS;
}
inline int cmp(db a, db b)
{
return sign(a - b);
}
struct P
{
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
// 重构加减乘除
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator<(P p) const
{
int c = cmp(x, p.x);
if (c)
return c == -1;
return cmp(y, p.y) == -1;
}
bool operator==(P o) const { return cmp(x, o.x) == 0 && cmp(y, o.y) == 0; }
db dot(P p) { return x * p.x + y * p.y; } // 点积
db det(P p) { return x * p.y - y * p.x; } // 叉积
db distTo(P p) { return (*this - p).abs(); }
db alpha() { return atan2(y, x); }
void read() { cin >> x >> y; }
void write() { cout << "(" << x << "," << y << ")" << endl; }
db abs() { return sqrt(abs2()); }
db abs2() { return x * x + y * y; }
P rot90() { return P(-y, x); }
P unit() { return *this / abs(); }
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
P rot(db an)
{
return {x * cos(an) - y * sin(an), x * sin(an) + y * cos(an)};
}
};
#define cross(p1, p2, p3) \
((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y))
#define crossOp(p1, p2, p3) sign(cross(p1, p2, p3))
// 直线 p1p2, q1q2 是否恰有一个交点
bool chkLL(P p1, P p2, P q1, P q2)
{
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return sign(a1 + a2) != 0;
}
// 求直线 p1p2, q1q2 的交点
P isLL(P p1, P p2, P q1, P q2)
{
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return (p1 * a2 + p2 * a1) / (a1 + a2);
}
// 判断区间 [l1, r1], [l2, r2] 是否相交
bool intersect(db l1, db r1, db l2, db r2)
{
if (l1 > r1)
swap(l1, r1);
if (l2 > r2)
swap(l2, r2);
return !(cmp(r1, l2) == -1 || cmp(r2, l1) == -1);
}
// 线段 p1p2, q1q2 相交
bool isSS(P p1, P p2, P q1, P q2)
{
return intersect(p1.x, p2.x, q1.x, q2.x) &&
intersect(p1.y, p2.y, q1.y, q2.y) &&
crossOp(p1, p2, q1) * crossOp(p1, p2, q2) <= 0 &&
crossOp(q1, q2, p1) * crossOp(q1, q2, p2) <= 0;
}
// 线段 p1p2, q1q2 严格相交
bool isSS_strict(P p1, P p2, P q1, P q2)
{
return crossOp(p1, p2, q1) * crossOp(p1, p2, q2) < 0 &&
crossOp(q1, q2, p1) * crossOp(q1, q2, p2) < 0;
}
// m 在 a 和 b 之间
bool isMiddle(db a, db m, db b)
{
/*if (a > b) swap(a, b);
return cmp(a, m) <= 0 && cmp(m, b) <= 0;*/
return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
bool isMiddle(P a, P m, P b)
{
return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}
// 点 p 在线段 p1p2 上
bool onSeg(P p1, P p2, P q)
{
return crossOp(p1, p2, q) == 0 && isMiddle(p1, q, p2);
}
// q1q2 和 p1p2 的交点 在 p1p2 上?
// 点 p 严格在 p1p2 上
bool onSeg_strict(P p1, P p2, P q)
{
return crossOp(p1, p2, q) == 0 &&
sign((q - p1).dot(p1 - p2)) * sign((q - p2).dot(p1 - p2)) < 0;
}
// 求 q 到 直线p1p2 的投影(垂足) ⚠️ : p1 != p2
P proj(P p1, P p2, P q)
{
P dir = p2 - p1;
return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
// 求 q 以 直线p1p2 为轴的反射
P reflect(P p1, P p2, P q)
{
return proj(p1, p2, q) * 2 - q;
}
// 求 q 到 线段p1p2 的最小距离
db nearest(P p1, P p2, P q)
{
if (p1 == p2)
return p1.distTo(q);
P h = proj(p1, p2, q);
if (isMiddle(p1, h, p2))
return q.distTo(h);
return min(p1.distTo(q), p2.distTo(q));
}
// 求 线段p1p2 与 线段q1q2 的距离
db disSS(P p1, P p2, P q1, P q2)
{
if (isSS(p1, p2, q1, q2))
return 0;
return min(min(nearest(p1, p2, q1), nearest(p1, p2, q2)),
min(nearest(q1, q2, p1), nearest(q1, q2, p2)));
}
// 极角排序
// sort(p, p + n, [&](P a, P b)
// {
// int qa = a.quad(), qb = b.quad();
// if (qa != qb)
// return qa < qb;
// else
// return sign(a.det(b)) > 0; });
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
typedef double db;
// 求多边形面积
db area(vector<P> ps)
{
db ret = 0;
rep(i, 0, ps.size()) ret += ps[i].det(ps[(i + 1) % ps.size()]);
return ret / 2;
}
// 点包含
int contain(vector<P> ps, P p)
{ // 2:inside,1:on_seg,0:outside
int n = ps.size(), ret = 0;
rep(i, 0, n)
{
P u = ps[i], v = ps[(i + 1) % n];
if (onSeg(u, v, p))
return 1;
if (cmp(u.y, v.y) <= 0)
swap(u, v);
if (cmp(p.y, u.y) > 0 || cmp(p.y, v.y) <= 0)
continue;
ret ^= crossOp(p, u, v) > 0;
}
return ret * 2;
}
// 严格凸包
vector<P> convexHull(vector<P> ps)
{
int n = ps.size();
if (n <= 1)
return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2);
int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0)
--k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0)
--k;
qs.resize(k - 1);
return qs;
}
// 不严格凸包
vector<P> convexHullNonStrict(vector<P> ps)
{
// caution: need to unique the Ps first
int n = ps.size();
if (n <= 1)
return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2);
int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0)
--k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0)
--k;
qs.resize(k - 1);
return qs;
}
// 旋转卡壳
db convexDiameter(vector<P> ps)
{
int n = ps.size();
if (n <= 1)
return 0;
int is = 0, js = 0;
rep(k, 1, n) is = ps[k] < ps[is] ? k : is, js = ps[js] < ps[k] ? k : js;
int i = is, j = js;
db ret = ps[i].distTo(ps[j]);
do
{
if ((ps[(i + 1) % n] - ps[i]).det(ps[(j + 1) % n] - ps[j]) >= 0)
(++j) %= n;
else
(++i) %= n;
ret = max(ret, ps[i].distTo(ps[j]));
} while (i != is || j != js);
return ret;
}
// 切多边形
vector<P> convexCut(const vector<P> &ps, P q1, P q2)
{
vector<P> qs;
int n = ps.size();
rep(i, 0, n)
{
P p1 = ps[i], p2 = ps[(i + 1) % n];
int d1 = crossOp(q1, q2, p1), d2 = crossOp(q1, q2, p2);
if (d1 >= 0)
qs.push_back(p1);
if (d1 * d2 < 0)
qs.push_back(isLL(p1, p2, q1, q2));
}
return qs;
}
#define rep(i, a, n) for (int i = a; i < n; i++)
const double PI = acos(-1.0);
// 判断两个圆的关系
int type(P o1, db r1, P o2, db r2)
{
db d = o1.distTo(o2);
if (cmp(d, r1 + r2) == 1)
return 4;
if (cmp(d, r1 + r2) == 0)
return 3;
if (cmp(d, abs(r1 - r2)) == 1)
return 2;
if (cmp(d, abs(r1 - r2)) == 0)
return 1;
return 0;
}
// 圆和线相交
vector<P> isCL(P o, db r, P p1, P p2)
{
if (cmp(abs((o - p1).det(p2 - p1) / p1.distTo(p2)), r) > 0)
return {};
db x = (p1 - o).dot(p2 - p1), y = (p2 - p1).abs2(),
d = x * x - y * ((p1 - o).abs2() - r * r);
d = max(d, (db)0.0);
P m = p1 - (p2 - p1) * (x / y), dr = (p2 - p1) * (sqrt(d) / y);
return {m - dr, m + dr}; // along dir: p1->p2
}
// 两个圆相交的交点
vector<P> isCC(P o1,
db r1,
P o2,
db r2)
{ // need to check whether two circles are the same
db d = o1.distTo(o2);
if (cmp(d, r1 + r2) == 1)
return {};
if (cmp(d, abs(r1 - r2)) == -1)
return {};
d = min(d, r1 + r2);
db y = (r1 * r1 + d * d - r2 * r2) / (2 * d), x = sqrt(r1 * r1 - y * y);
P dr = (o2 - o1).unit();
P q1 = o1 + dr * y, q2 = dr.rot90() * x;
return {q1 - q2, q1 + q2}; // along circle 1
}
// 求切线,默认求外公切线,求内公切线的话,r2改成负数,求点到圆的切线,r2改成0
// extanCC, intanCC : -r2, tanCP : r2 = 0
vector<pair<P, P>> tanCC(P o1, db r1, P o2, db r2)
{
P d = o2 - o1;
db dr = r1 - r2, d2 = d.abs2(), h2 = d2 - dr * dr;
if (sign(d2) == 0 || sign(h2) < 0)
return {};
h2 = max((db)0.0, h2);
vector<pair<P, P>> ret;
for (db sign : {-1, 1})
{
P v = (d * dr + d.rot90() * sqrt(h2) * sign) / d2;
ret.push_back({o1 + v * r1, o2 + v * r2});
}
if (sign(h2) == 0)
ret.pop_back();
return ret;
}
db rad(P p1, P p2)
{
return atan2l(p1.det(p2), p1.dot(p2));
}
// 圆和三角形的面积交
db areaCT(db r, P p1, P p2)
{
vector<P> is = isCL(P(0, 0), r, p1, p2);
if (is.empty())
return r * r * rad(p1, p2) / 2;
bool b1 = cmp(p1.abs2(), r * r) == 1, b2 = cmp(p2.abs2(), r * r) == 1;
if (b1 && b2)
{
P md = (is[0] + is[1]) / 2;
if (sign((p1 - md).dot(p2 - md)) <= 0)
return r * r * (rad(p1, is[0]) + rad(is[1], p2)) / 2 +
is[0].det(is[1]) / 2;
else
return r * r * rad(p1, p2) / 2;
}
if (b1)
return (r * r * rad(p1, is[0]) + is[0].det(p2)) / 2;
if (b2)
return (p1.det(is[1]) + r * r * rad(is[1], p2)) / 2;
return p1.det(p2) / 2;
}
// 内心
P inCenter(P A, P B, P C)
{
double a = (B - C).abs(), b = (C - A).abs(), c = (A - B).abs();
return (A * a + B * b + C * c) / (a + b + c);
}
// 外心
P circumCenter(P a, P b, P c)
{
P bb = b - a, cc = c - a;
double db = bb.abs2(), dc = cc.abs2(), d = 2 * bb.det(cc);
return a - P(bb.y * dc - cc.y * db, cc.x * db - bb.x * dc) / d;
}
// 垂心
P othroCenter(P a, P b, P c)
{
P ba = b - a, ca = c - a, bc = b - c;
double Y = ba.y * ca.y * bc.y, A = ca.x * ba.y - ba.x * ca.y,
x0 = (Y + ca.x * ba.y * b.x - ba.x * ca.y * c.x) / A,
y0 = -ba.x * (x0 - c.x) / ba.y + ca.y;
return {x0, y0};
}
// 最小圆覆盖,随机增量法
pair<P, db> min_circle(vector<P> ps)
{
random_device rd;
mt19937 rng(rd());
shuffle(ps.begin(), ps.end(), rng);
// random_shuffle(ps.begin(), ps.end());
int n = ps.size();
P o = ps[0];
db r = 0;
rep(i, 1, n) if (o.distTo(ps[i]) > r + EPS)
{
o = ps[i], r = 0;
rep(j, 0, i) if (o.distTo(ps[j]) > r + EPS)
{
o = (ps[i] + ps[j]) / 2;
r = o.distTo(ps[i]);
rep(k, 0, j) if (o.distTo(ps[k]) > r + EPS)
{
o = circumCenter(ps[i], ps[j], ps[k]);
r = o.distTo(ps[i]);
}
}
}
return {o, r};
}
db intergal(db x, db y, db r, db L, db R)
{
return r * r * (R - L) + x * r * (sinl(R) - sinl(L)) +
y * r * (-cosl(R) + cosl(L));
}
db calc_area_circle(P c, db r, db L, db R)
{
return intergal(c.x, c.y, r, L, R) / 2;
}
db norm(db x)
{
while (x < 0)
x += 2 * PI;
while (x > 2 * PI)
x -= 2 * PI;
return x;
}
// 圆面积并
// const int N = 10010;
// P cs[N];
// db rs[N];
// void work()
// {
// vector<int> cand = {};
// rep(i, 0, n)
// {
// bool ok = 1;
// rep(j, 0, n) if (i != j)
// {
// if (rs[j] > rs[i] + EPS &&
// rs[i] + cs[i].distTo(cs[j]) <= rs[j] + EPS)
// {
// ok = 0;
// break;
// }
// if (cs[i] == cs[j] && cmp(rs[i], rs[j]) == 0 && j < i)
// {
// ok = 0;
// break;
// }
// }
// if (ok)
// cand.push_back(i);
// }
// rep(i, 0, cand.size()) cs[i] = cs[cand[i]], rs[i] = rs[cand[i]];
// n = cand.size();
// db area = 0;
// // work
// rep(i, 0, n)
// {
// vector<pair<db, int>> ev = {{0, 0}, {2 * PI, 0}};
// int cur = 0;
// rep(j, 0, n) if (j != i)
// {
// auto ret = isCC(cs[i], rs[i], cs[j], rs[j]);
// if (!ret.empty())
// {
// db l = (ret[0] - cs[i]).alpha();
// db r = (ret[1] - cs[i]).alpha();
// l = norm(l);
// r = norm(r);
// ev.push_back({l, 1});
// ev.push_back({r, -1});
// if (l > r)
// ++cur;
// }
// }
// sort(ev.begin(), ev.end());
// rep(j, 0, ev.size() - 1)
// {
// cur += ev[j].second;
// if (cur == 0)
// {
// area += calc_area_circle(cs[i], rs[i], ev[j].fi, ev[j + 1].fi);
// }
// }
// }
// }
void solve()
{
int n;
cin >> n;
vector<P> ps;
fr(i, 1, n)
{
P p;
cin >> p.x >> p.y;
ps.push_back(p);
}
auto cv = convexHull(ps);
set<pii> on_convex;
for (auto now : cv)
{
on_convex.insert({now.x, now.y});
}
vector<P> inside;
for (int i = 0; i < n; i++)
{
if (contain(cv, ps[i]) == 2)
{
inside.push_back(ps[i]);
}
}
if (inside.size() == 0)
{
cout << "1" << endl;
return;
}
// cout << inside.size() << endl;
int ans = 0;
for (auto now : inside)
{
// cout << now.x << " " << now.y << " ";
vector<P> t;
for (int i = 0; i < n; i++)
{
if (ps[i] == now)
continue;
t.push_back(ps[i]);
}
sort(t.begin(), t.end(), [&](P a, P b)
{ return atan2(a.y - now.y, a.x - now.x) < atan2(b.y - now.y, b.x - now.x); });
int sz = t.size();
for (int i = 0; i < sz; i++)
{
bool t1 = on_convex.count({t[i % sz].x, t[i % sz].y});
bool t2 = on_convex.count({t[(i + 1) % sz].x, t[(i + 1) % sz].y});
if (t1 && t2)
{
ans++;
}
}
// cout << ans << endl;
}
cout << ans + 1 << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1;
if (_output)
cin >> _;
while (_--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4100kb
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: 3856kb
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: 1ms
memory: 3752kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4012kb
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: 1ms
memory: 3760kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Time Limit Exceeded
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...