QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#298750#7906. Almost Convexucup-team918#WA 7ms3908kbC++172.5kb2024-01-06 14:29:472024-01-06 14:29:48

Judging History

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

  • [2024-01-06 14:29:48]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3908kb
  • [2024-01-06 14:29:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const double pi = acos(-1);
int n, vis[2010];
pair<int, int> a[2010];
double val[2010];
int calc(pair<int, int> i, pair<int, int> j, pair<int, int> k) {
	return (j.first - i.first) * (k.second - i.second) - (j.second - i.second) * (k.first - i.first);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].first >> a[i].second;
	sort(a + 1, a + n + 1);
	vector<int> u, d, p;
	u.push_back(1), d.push_back(1);
	for (int i = 2; i <= n; i++) {
		while (u.size() > 1) {
			int j = u.back(), k = u[u.size() - 2];
			if (calc(a[k], a[j], a[i]) > 0) u.pop_back();
			else break;
		}
		u.push_back(i);
		while (d.size() > 1) {
			int j = d.back(), k = d[d.size() - 2];
			if (calc(a[k], a[j], a[i]) < 0) d.pop_back();
			else break;
		}
		d.push_back(i);
	}
	for (int x : u) vis[x] = 1;
	for (int x : d) vis[x] = 1;
	for (int i = 1; i <= n; i++)
		if (!vis[i]) p.push_back(i);
	int ans = 1;
	for (int i = 1; i < d.size(); i++) {
		int o = d[i - 1], v = d[i];
		double t = atan2(a[v].second - a[o].second, a[v].first - a[o].first);
		for (int x : p) {
			val[x] = atan2(a[x].second - a[o].second, a[x].first - a[o].first);
			val[x] -= t;
			if (val[x] < 0) val[x] += pi * 2;
		}
		sort(p.begin(), p.end(), [&](int x, int y) {
			return val[x] > val[y];
		});
		stack<int> st;
		for (int x : p) {
			while (!st.empty()) {
				int y = st.top();
				if (calc(a[o], a[y], a[x]) > 0 && calc(a[v], a[x], a[y]) > 0)
					st.pop();
				else break;
			}
			if (!st.empty()) {
				int y = st.top();
				if (calc(a[o], a[x], a[y]) > 0 && calc(a[v], a[y], a[x]) > 0)
					continue;
			}
			st.push(x);
		}
		ans += st.size();
	}
	for (int i = 1; i < u.size(); i++) {
		int o = u[i], v = u[i - 1];
		double t = atan2(a[v].second - a[o].second, a[v].first - a[o].first);
		for (int x : p) {
			val[x] = atan2(a[x].second - a[o].second, a[x].first - a[o].first);
			val[x] -= t;
			if (val[x] < 0) val[x] += pi * 2;
		}
		sort(p.begin(), p.end(), [&](int x, int y) {
			return val[x] > val[y];
		});
		stack<int> st;
		for (int x : p) {
			while (!st.empty()) {
				int y = st.top();
				if (calc(a[o], a[y], a[x]) > 0 && calc(a[v], a[x], a[y]) > 0)
					st.pop();
				else break;
			}
			if (!st.empty()) {
				int y = st.top();
				if (calc(a[o], a[x], a[y]) > 0 && calc(a[v], a[y], a[x]) > 0)
					continue;
			}
			st.push(x);
		}
		ans += st.size();
	}
	cout << ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3856kb

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 7ms
memory: 3908kb

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:

18950

result:

wrong answer 1st numbers differ - expected: '718', found: '18950'