QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303799#7906. Almost Convexigor_the_creatorTL 0ms4036kbC++172.3kb2024-01-13 00:19:332024-01-13 00:19:35

Judging History

This is the latest submission verdict.

  • [2024-01-13 00:19:35]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 4036kb
  • [2024-01-13 00:19:33]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e3 + 5;
const int Mod = 998244353;

int xx, yy;
bool vis[N];

struct dot{
	int x, y, id, idx;
}d[N], e[N], stac[N];

int cross(dot a, dot b, dot c) // ������ 
{
	return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp2(dot a, dot b)
{
	if (atan2(a.y - yy, a.x - xx) != atan2(b.y - yy, b.x - xx)) {
		return atan2(a.y - yy, a.x - xx) < atan2(b.y - yy, b.x - xx);
	}
	return a.x < b.x;
}

bool cmp1(dot a, dot b)
{
	return (a.y == b.y) ? (a.x < b.x) : (a.y < b.y);
}

signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n, top = 0, ans = 1;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> d[i].x >> d[i].y;
	}
	sort(d + 1, d + n + 1, cmp1);
	stac[++top] = {d[1].x, d[1].y, 1, 1};
	vis[1] = 1;
	xx = d[1].x; yy = d[1].y;
	sort(d + 2, d + n + 1, cmp2);
	stac[++top] = {d[2].x, d[2].y, 2, 2};
	vis[2] = 1;
	for (int i = 1; i <= n; ++i) {
		e[i] = {d[i].x, d[i].y, i, i};
	}
	for (int i = 3; i <= n; ++i) {
		while (top >= 2 && cross(d[stac[top - 1].id], d[stac[top].id], d[i]) < 0) {
			vis[stac[top].id] = 0;
			--top;
		}
		stac[++top] = {d[i].x, d[i].y, i, top};
		vis[stac[top].id] = 1;
	}
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue;
		xx = d[i].x; yy = d[i].y;
		sort(e + 1, e + n + 1, cmp2);
		/*cout << xx << " , " << yy << "&&\n";
		for (int j = 1; j <= n; ++j) {
			cout << j  << "(" << e[j].x << ", " << e[j].y << ") :" << atan2(e[j].y - yy, e[j].x - xx) << "##\n";
		}*/
		for (int j = 1; j < n; ++j) {
		//	cout << atan2(stac[j].y - yy, stac[j].x - xx) << " * " << atan2(stac[j + 1].y - yy, stac[j + 1].x - xx) << "\n";
		//	int res = abs(e[j].idx - e[j + 1].idx);
			if (e[j].id == i) continue;
			if (vis[e[j].idx] && (vis[e[j + 1].idx] || (e[j + 1].id == i && vis[e[j + 2].id]))) {
				++ans;
			/*	cout << "(" << e[j].x << ", " << e[j].y << ") - ";
				cout << "(" << d[i].x << ", " << d[i].y << ") - ";
				cout << "(" << e[j + 1].x << ", " << e[j + 1].y << ")\n";*/
			}
		}
		if (e[1].id == i) {
			if (vis[e[2].id] && vis[e[n].id]) ++ans;
		}
		else if (e[n].id == i) {
			if (vis[e[1].id] && vis[e[n - 1].id]) ++ans;
		}
		else {
			if (vis[e[1].id] && vis[e[n].id]) ++ans;
		}
	}
	cout << ans;
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3948kb

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: 4036kb

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: 3628kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3876kb

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: 3976kb

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...

output:


result: