QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#520939 | #4371. Spin Doctor | mshcherba | WA | 71ms | 8632kb | C++20 | 4.9kb | 2024-08-15 17:44:28 | 2024-08-15 17:44:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
struct Pt
{
int x, y;
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.y};
}
};
LL sq(const Pt& p)
{
return (LL)p.x * p.x + (LL)p.y * p.y;
}
int sgn(LL x)
{
return (0 < x) - (x < 0);
}
LL dot(const Pt& p, const Pt& q)
{
return (LL)p.x * p.x + (LL)p.y * p.y;
}
LL cross(const Pt& p, const Pt& q)
{
return (LL)p.x * q.y - (LL)p.y * q.x;
}
LL orient(const Pt& p, const Pt& q, const Pt& r)
{
return cross(q - p, r - p);
}
bool half(const Pt& p)
{
assert(sgn(p.x) != 0 || sgn(p.y) != 0);
return sgn(p.y) == -1 ||
(sgn(p.y) == 0 && sgn(p.x) == -1);
}
void polarSortAround(const Pt& o, vector<pair<Pt, int>>& v)
{
sort(ALL(v), [o](pair<Pt, int> pp, pair<Pt, int> qq)
{
Pt p = pp.F - o;
Pt q = qq.F - o;
bool hp = half(p), hq = half(q);
if (hp != hq)
return hp < hq;
int s = sgn(cross(p, q));
if (s != 0)
return s == 1;
return sq(p) < sq(q);
});
}
bool inDisk(const Pt& a, const Pt& b, const Pt& p)
{
return sgn(dot(a - p, b - p)) <= 0;
}
bool onSegment(const Pt& a, const Pt& b, const Pt& p)
{
return sgn(orient(a, b, p)) == 0 && inDisk(a, b, p);
}
bool inConvexPolygon(const vector<Pt>& v, const Pt& a)
{
assert(SZ(v) >= 2);
if (SZ(v) == 2)
return onSegment(v[0], v[1], a);
if (sgn(orient(v.back(), v[0], a)) < 0
|| sgn(orient(v[0], v[1], a)) < 0)
return false;
int i = lower_bound(v.begin() + 2, v.end(), a,
[&](const Pt& p, const Pt& q)
{
return sgn(orient(v[0], p, q)) > 0;
}) - v.begin();
return sgn(orient(v[i - 1], v[i], a)) >= 0;
}
vector<Pt> convexHull(vector<Pt> v)
{
if (SZ(v) <= 1)
return v;
sort(ALL(v), [](const Pt& p, const Pt& q)
{
int dx = sgn(p.x - q.x);
if (dx != 0)
return dx < 0;
return sgn(p.y - q.y) < 0;
});
vector<Pt> lower, upper;
for (const Pt& p : v)
{
while (SZ(lower) > 1
&& sgn(orient(lower[SZ(lower) - 2], lower.back(), p)) <= 0)
lower.pop_back();
while (SZ(upper) > 1
&& sgn(orient(upper[SZ(upper) - 2], upper.back(), p)) >= 0)
upper.pop_back();
lower.PB(p);
upper.PB(p);
}
reverse(ALL(upper));
lower.insert(lower.end(), next(upper.begin()), prev(upper.end()));
return lower;
}
PII tangetsToConvexPolygon(const vector<Pt>& v, const Pt& p)
{
int n = SZ(v), i = 0;
if (n == 2)
return {0, 1};
while (sgn(orient(p, v[i], v[(i + 1) % n]))
* sgn(orient(p, v[i], v[(i + n - 1) % n])) > 0)
i++;
int s1 = 1, s2 = -1;
if (sgn(orient(p, v[i], v[(i + 1) % n])) == s1
|| sgn(orient(p, v[i], v[(i + n - 1) % n])) == s2)
swap(s1, s2);
PII res;
int l = i, r = i + n - 1;
while (r - l > 1)
{
int m = (l + r) / 2;
if (sgn(orient(p, v[i], v[m % n])) != s1
&& sgn(orient(p, v[m % n], v[(m + 1) % n])) != s1)
l = m;
else
r = m;
}
res.F = r % n;
l = i;
r = i + n - 1;
while (r - l > 1)
{
int m = (l + r) / 2;
if (sgn(orient(p, v[i], v[m % n])) == s2
|| sgn(orient(p, v[m % n], v[(m + 1) % n])) != s2)
l = m;
else
r = m;
}
res.S = r % n;
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<Pt> v[2];
FOR(i, 0, n)
{
Pt p;
int c;
cin >> p.x >> p.y >> c;
v[c].PB(p);
}
vector<Pt> hull = convexHull(v[1]);
if (SZ(hull) == 1)
{
int ans = SZ(v[1]);
if (ans == 1)
{
cout << "1\n";
return 0;
}
for (const Pt& p : v[0])
{
if (p.x == hull[0].x && p.y == hull[0].y)
ans++;
}
cout << ans << "\n";
return 0;
}
int cntFalseInside = 0;
vector<pair<Pt, int>> events;
int cur = 0;
for (const Pt& p : v[0])
{
if (inConvexPolygon(hull, p))
cntFalseInside++;
else
{
auto [i1, i2] = tangetsToConvexPolygon(hull, p);
// assert(sgn(orient(p, hull[i1], hull[i2])) != 0);
if (sgn(orient(p, hull[i1], hull[i2])) < 0)
swap(i1, i2);
events.PB({hull[i1] - p, 1});
events.PB({hull[i2] - p, -1});
events.PB({p - hull[i1], 1});
events.PB({p - hull[i2], -1});
if ((hull[i1] - p).y <= 0 && (hull[i2] - p).y >= 0)
cur++;
else if ((p - hull[i1]).y <= 0 && (p - hull[i2]).y >= 0)
cur++;
}
}
polarSortAround({0, 0}, events);
int ans = cur;
for (int i = 0; i < SZ(events); )
{
int j = i;
while (j < SZ(events) && sgn(cross(events[i].F, events[j].F)) == 0 && sgn(dot(events[i].F, events[j].F)) > 0)
{
if (!(events[j].F.x > 0 && events[j].F.y == 0 && events[j].S == 1))
cur += events[j].S;
j++;
}
ans = min(ans, cur);
i = j;
}
cout << ans + SZ(v[1]) + cntFalseInside << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
6 0 10 0 10 0 1 12 8 1 5 5 0 11 2 1 11 3 0
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
10 6 1 1 0 2 0 2 1 1 6 1 1 8 2 0 4 4 0 4 0 0 2 3 1 6 1 0 6 3 1
output:
8
result:
ok single line: '8'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 5 7 0 3 4 0 5 7 0 5 7 1 9 4 0
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
100 7487 4751 1 7499 5064 1 7471 5376 1 7404 5683 1 7300 5979 1 7159 6260 1 6984 6520 1 6777 6757 1 6543 6966 1 6284 7144 1 6006 7288 1 5711 7396 1 5405 7466 1 5092 7498 1 4780 7490 1 4469 7442 1 4167 7357 1 3878 7234 1 3607 7075 1 3358 6884 1 3135 6664 1 2941 6417 1 2780 6147 1 2653 5860 1 2564 555...
output:
61
result:
ok single line: '61'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
200 7489 1285 0 6851 8471 0 6122 2766 1 2413 9338 0 1725 7382 0 6984 6520 1 5080 8417 0 2604 5711 1 5833 2643 1 48 2810 0 5316 2439 0 900 7419 0 6809 867 0 6006 7288 1 5092 7498 1 5531 2558 1 7075 6393 1 9979 9313 0 7436 4441 1 4595 2534 1 2598 909 0 842 284 0 3358 6884 1 6522 7976 0 604 5833 0 3607...
output:
125
result:
ok single line: '125'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
300 2253 823 1 1865 9556 0 306 6720 1 8588 1519 1 2756 9468 1 5810 9933 1 1625 9138 0 27 932 0 8124 1097 1 8699 8363 1 7202 9489 1 9420 7337 1 9862 6164 1 908 2128 1 9341 2521 1 372 8140 0 9318 7520 1 1760 34 0 785 612 0 1445 1442 0 9694 3280 1 9496 2152 0 9249 1891 0 2162 9828 0 580 2663 1 1269 832...
output:
234
result:
ok single line: '234'
Test #7:
score: 0
Accepted
time: 64ms
memory: 7940kb
input:
100000 7487 4751 1 7487 4751 1 7487 4752 1 7487 4752 1 7487 4752 1 7487 4752 1 7487 4753 1 7487 4753 1 7487 4753 1 7487 4754 1 7487 4754 1 7487 4754 1 7487 4755 1 7487 4755 1 7487 4755 1 7487 4756 1 7488 4756 1 7488 4756 1 7488 4757 1 7488 4757 1 7488 4757 1 7488 4757 1 7488 4758 1 7488 4758 1 7488 ...
output:
68833
result:
ok single line: '68833'
Test #8:
score: 0
Accepted
time: 60ms
memory: 7120kb
input:
100000 8980 4601 1 8980 4602 1 8980 4602 1 8980 4603 1 8980 4603 1 8980 4604 1 8980 4604 1 8980 4605 1 8980 4605 1 8980 4606 1 8980 4606 1 8980 4607 1 8980 4607 1 8980 4608 1 8980 4608 1 8980 4609 1 8980 4609 1 8980 4610 1 8980 4610 1 8980 4611 1 8981 4611 1 8981 4612 1 8981 4612 1 8981 4613 1 8981 ...
output:
79761
result:
ok single line: '79761'
Test #9:
score: 0
Accepted
time: 64ms
memory: 8632kb
input:
100000 9975 4501 1 9975 4502 1 9975 4503 1 9975 4503 1 9975 4504 1 9975 4504 1 9975 4505 1 9975 4506 1 9975 4506 1 9975 4507 1 9975 4508 1 9975 4508 1 9975 4509 1 9975 4509 1 9975 4510 1 9975 4511 1 9976 4511 1 9976 4512 1 9976 4513 1 9976 4513 1 9976 4514 1 9976 4514 1 9976 4515 1 9976 4516 1 9976 ...
output:
79877
result:
ok single line: '79877'
Test #10:
score: 0
Accepted
time: 71ms
memory: 7164kb
input:
100000 89749 223387 0 295171 424382 0 397151 279092 1 393939 207794 1 109069 198636 1 338201 128673 1 388987 306412 1 401174 201459 0 428943 426416 0 292775 106229 1 181076 383227 1 207577 106125 1 389057 405639 0 358258 146173 1 376103 425370 0 284279 396030 1 342155 368352 1 479748 52614 0 102762 ...
output:
72070
result:
ok single line: '72070'
Test #11:
score: 0
Accepted
time: 71ms
memory: 8344kb
input:
100000 649 24758 0 14496 41252 0 39286 10853 0 19975 37285 1 40085 29490 0 1766 27831 0 5842 586 0 27105 8225 1 11312 32491 1 17523 4856 0 16990 8550 1 4916 12992 0 7696 24913 1 42700 5177 0 43755 27268 0 9922 42370 0 8555 16976 1 17794 36896 0 21532 37468 1 35271 30549 0 31468 10477 1 37030 18776 1...
output:
74280
result:
ok single line: '74280'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 100 100 1 500 500 1 200 200 0
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
5 0 100 0 0 200 1 0 300 0 0 400 1 0 500 0
output:
3
result:
ok single line: '3'
Test #14:
score: -100
Wrong Answer
time: 0ms
memory: 3656kb
input:
7 100 0 0 200 0 1 300 0 0 400 0 1 500 0 0 600 0 1 700 0 0
output:
3
result:
wrong answer 1st lines differ - expected: '5', found: '3'