QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293118 | #7906. Almost Convex | Sy03 | TL | 0ms | 4112kb | C++20 | 8.5kb | 2023-12-28 21:53:10 | 2023-12-28 21:53:11 |
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 long long 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 {0, 0};
}
};
#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; });
const db eps = 1e-8;
struct argcmp
{
bool operator()(P &a, P &b) const
{
const auto quad = [](const P &a)
{
if (a.y < -eps)
return 1;
if (a.y > eps)
return 4;
if (a.x < -eps)
return 5;
if (a.x > eps)
return 3;
return 2;
};
const int qa = quad(a), qb = quad(b);
if (qa != qb)
return qa < qb;
db t = a.det(b);
// if (abs(t)<=eps) return a*a<b*b-eps; // 不同长度的向量需要分开
return t > eps;
}
};
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
// 求多边形面积
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;
}
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: 3964kb
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: 4112kb
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: 3632kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3984kb
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: 3772kb
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...