oj.uz

Submission #130453

# Submission time Handle Problem Language Result Execution time Memory
130453 2019-07-15T08:25:42 Z 이온조(#3149) Fence (CEOI08_fence) C++14
100 / 100
 583 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
#define sz(V) ((int)V.size())

int CCW(pii A, pii B, pii C) {
	int tmp = A.X*B.Y + B.X*C.Y + C.X*A.Y - A.Y*B.X - B.Y*C.X - C.Y*A.X;
	if(tmp < 0) return -1;
	if(tmp > 0) return +1;
}

int N, M;
pii H[111], T[111];
bool O[111];

int get() {
	int c = 0;
	for(int i=1; i<=N; i++) if(O[i]) ++c;
	if(c < 3) return 1e9;
	
	vector<pii> S, C;
	int mn = 1e9, st = -1;
	for(int i=1; i<=N; i++) if(O[i] && mn > H[i].X) mn = H[i].X, st = i;
	for(int i=1; i<=N; i++) if(O[i] && st != i) S.push_back(H[i]);
	sort(S.begin(), S.end(), [&](pii PP, pii QQ) { return CCW(H[st], PP, QQ) == -1; });
	C.push_back(H[st]);
	for(auto& it: S) {
		while(sz(C) >= 2 && CCW(C[sz(C) - 2], C[sz(C) - 1], it) == +1) C.pop_back();
		C.push_back(it);
	}
	// puts("Hull:");
	// for(int i=0; i<sz(C); i++) printf("%d %d\n", C[i].X, C[i].Y);
	// puts("---------------------");

	int cnt = 0;
	for(int i=1; i<=M; i++) {
		bool f = 1;
		for(int j=0; j<sz(C); j++) {
			pii a = C[j], b = C[(j+1) % sz(C)];
			if(CCW(a, b, T[i]) == +1) f = 0;
		}
		if(f) ++cnt;
	}

	return 111 * (M - cnt) + 20 * sz(C);
}

int main() {
	srand(12345);
	scanf("%d%d",&N,&M);
	for(int i=1; i<=N; i++) scanf("%d%d", &H[i].X, &H[i].Y);
	for(int i=1; i<=M; i++) scanf("%d%d", &T[i].X, &T[i].Y);
	int ans = 111 * M;
	O[1] = O[2] = O[3] = 1;
	for(int i=1; i<=500; i++) {
		int mn = 1e9, mni = -1;
		for(int j=1; j<=100; j++) {
			int k = rand() % N + 1;
			O[k] ^= 1;
			int tmp = get();
			if(mn > tmp) mn = tmp, mni = k;
			O[k] ^= 1;
		}
		if(mni != -1) O[mni] ^= 1;
		ans = min(ans, get());

		// printf("val: %d\n", get());
		// for(int j=1; j<=N; j++) printf("%d", O[j]);
		// puts("");
	}
	for(int i=1; i<=N; i++) {
		for(int j=i+1; j<=N; j++) {
			for(int k=j+1; k<=N; k++) {
				int a = i, b = j, c = k;
				if(CCW(H[a], H[b], H[c]) != -1) swap(b, c);
				int cnt = 0;
				for(int p=1; p<=M; p++) {
					if(CCW(H[a], H[b], T[p]) == -1 && CCW(H[b], H[c], T[p]) == -1 && CCW(H[c], H[a], T[p]) == -1) ++cnt;
				}
				ans = min(ans, (M - cnt) * 111 + 60);
			}
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message

fence.cpp: In function 'int CCW(pii, pii, pii)':
fence.cpp:12:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
fence.cpp: In function 'int main()':
fence.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~
fence.cpp:53:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d%d", &H[i].X, &H[i].Y);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fence.cpp:54:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=M; i++) scanf("%d%d", &T[i].X, &T[i].Y);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 360 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 360 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 356 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 360 KB Output is correct
2 Correct 144 ms 256 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 356 KB Output is correct
2 Correct 156 ms 392 KB Output is correct