Submission #130462

#	Time	Username	Problem	Language	Result	Execution time	Memory
130462		onjo0127	Fence (CEOI08_fence)	C++11	100 / 100	584 ms	504 KiB

fence

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10