oj.uz

Submission #130364

# Submission time Handle Problem Language Result Execution time Memory
130364 2019-07-15T03:43:18 Z 윤교준(#3150) Fence (CEOI08_fence) C++14
100 / 100
 24 ms 380 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int operator * (const pii &a, const pii &b) { return a.first*b.second - b.first*a.second; }
int ccw(const pii &a, const pii &b, const pii &c) { return a*b + b*c + c*a; }

int D[105];

pii A[105], B[105];

int Ans = INF;
int N, M;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= N; i++) cin >> A[i].first >> A[i].second;
	for(int i = 1; i <= M; i++) cin >> B[i].first >> B[i].second;

	for(int i = 1; i <= N; i++) {
		fill(D, D+N+1, INF);
		vector<int> AO, BO;
		for(int j = 1; j <= N; j++) if(A[i] < A[j]) AO.eb(j);
		for(int j = 1; j <= M; j++) if(A[i] < B[j]) BO.eb(j);
		sort(allv(AO), [&](int a, int b) { return 0 < ccw(A[i], A[a], A[b]); });
		sort(allv(BO), [&](int a, int b) { return 0 < ccw(A[i], B[a], B[b]); });
		for(int oi = 0, oj = 0, n = sz(AO), m = sz(BO); oi < n; oi++) {
			upmin(D[oi], 40);
			for(; oj < m && ccw(A[i], A[AO[oi]], B[BO[oj]]) <= 0; oj++);
			for(int ni = oi+1; ni < n; ni++) {
				int cnt = 0;
				for(int nj = oj; nj < m && ccw(A[i], A[AO[ni]], B[BO[nj]]) <= 0; nj++) {
					if(0 < ccw(A[AO[oi]], A[AO[ni]], B[BO[nj]])) cnt++;
				}
				upmin(D[ni], D[oi] + 20 - 111*cnt);
			}
			upmin(Ans, D[oi]);
		}
	}

	cout << min(0, Ans) + M*111 << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct