oj.uz

답안 #130427

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130427 2019-07-15T07:51:39 Z 임유진(#3151) Fence (CEOI08_fence) C++14
40 / 100
 2 ms 376 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 105
#define fi first
#define se second

typedef pair<int, int> pii;

int N, M;
pii h[MAXN], t[MAXN];
vector<pii> ch;

int ccw(pii a, pii b, pii c) {
	return a.fi * b.se - a.se * b.fi + b.fi * c.se - b.se * c.fi + c.fi * a.se - c.se * a.fi;
}

bool chkin(pii a, pii b, pii c, pii d) {
	return ccw(a, b, d) > 0 && ccw(b, c, d) > 0 && ccw(c, a, d) > 0;
}

bool chktree(pii a, pii b, pii c) {
	for(int i = 0; i < M; i++) if(chkin(a, b, c, t[i])) return true;
	return false;
}

int main() {
	scanf("%d%d", &N, &M);
	for(int i = 0; i < N; i++) scanf("%d%d", &h[i].fi, &h[i].se);
	for(int i = 0; i < M; i++) scanf("%d%d", &t[i].fi, &t[i].se);

	sort(h, h + N);
	vector<pii> lc, uc;
	lc.push_back(h[0]);
	lc.push_back(h[1]);
	for(int i = 2; i < N; i++) {
		while(lc.size() > 1 && ccw(lc[lc.size() - 2], lc.back(), h[i]) <= 0) lc.pop_back();
		lc.push_back(h[i]);
	}
	uc.push_back(h[0]);
	uc.push_back(h[1]);
	for(int i = 2; i < N; i++) {
		while(uc.size() > 1 && ccw(uc[uc.size() - 2], uc.back(), h[i]) >= 0) uc.pop_back();
		uc.push_back(h[i]);
	}

	ch.insert(ch.end(), lc.begin(), lc.end());
	for(int i = uc.size() - 2; i > 0; i--) ch.push_back(uc[i]);

	for(int i = 0; i < N && ch.size() > 2; i++) {
		vector<pii> v;
		if(!chktree(ch.back(), ch[0], ch[1])) {
			v.insert(v.end(), ch.begin() + 1, ch.end());
			swap(v, ch);
			continue;
		}
		if(!chktree(ch[ch.size() - 2], ch.back(), ch[0])) {
			ch.pop_back();
			continue;
		}
		for(int j = 1; j < ch.size() - 2; j++) {
			if(!chktree(ch[j - 1], ch[j], ch[j + 1])) {
				v.insert(v.end(), ch.begin(), ch.begin() + j);
				v.insert(v.end(), ch.begin() + j + 1, ch.end());
				swap(v, ch);
				break;
			}
		}
	}

	if(ch.size() < 3) {
		printf("%d", 111 * M);
		return 0;
	}

	int cnt = 0;
	for(int i = 0; i < M; i++) {
		if(ccw(t[i], ch.back(), ch[0]) < 0) {
			cnt++;
			continue;
		}
		for(int j = 0; j < ch.size() - 1; j++) if(ccw(t[i], ch[j], ch[j + 1]) < 0) {
			cnt++;
			break;
		}
	}

	printf("%d", 111 * cnt + 20 * int(ch.size()));
	return 0;
}

Compilation message

fence.cpp: In function 'int main()':
fence.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1; j < ch.size() - 2; j++) {
                  ~~^~~~~~~~~~~~~~~
fence.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < ch.size() - 1; j++) if(ccw(t[i], ch[j], ch[j + 1]) < 0) {
                  ~~^~~~~~~~~~~~~~~
fence.cpp:31: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:32:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) scanf("%d%d", &h[i].fi, &h[i].se);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fence.cpp:33:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < M; i++) scanf("%d%d", &t[i].fi, &t[i].se);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct