QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#520939#4371. Spin DoctormshcherbaWA 71ms8632kbC++204.9kb2024-08-15 17:44:282024-08-15 17:44:29

Judging History

你现在查看的是最新测评结果

  • [2024-08-15 17:44:29]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:8632kb
  • [2024-08-15 17:44:28]
  • 提交

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'