oj.uz

답안 #96936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96936 2019-02-12T19:37:53 Z kyn01286 공룡 발자국 (KOI18_footprint) C++14
14 / 100
 57 ms 768 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, X, Y;
vector< pair<int,int> > point;

int sign(int a) {
	return a<0?-1:1;
}

bool cmp(pair<int,int> p1, pair<int,int> p2) {
	double d1 = ((double)X-p1.first)/(Y-p1.second);
	double d2 = ((double)X-p2.first)/(Y-p2.second);
	return d1 < d2;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	
	cin >> N;
	int y_min = 100000001, y_index;
	for(int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		if(b < y_min) {
			y_min = b;
			y_index = i;
		}
		point.push_back(make_pair(a,b));
	}
	X = point[y_index].first; Y = point[y_index].second; // 뒤꿈치 좌표
	point.erase(point.begin()+y_index);
	sort(point.begin(), point.end(), cmp);
	pair<int, vector< pair<int,int> > > p[point.size()]; // 가능한 발가락 수 저장
	int p_prev[point.size()]; // 전 발가락 인덱스 저장 
	for(int i = 0; i < point.size(); i++) {
		p[i].first = 0;
		p_prev[i] = -1;
	}
	/*
	for(int i = 0; i < point.size(); i++) {
		cout << point[i].first << ',' << point[i].second << '\n';
	}
	*/
	for(int i = 0; i < point.size()-2; i++) { // 처음 점부터 
		for(int j = i+2; j < point.size(); j++) { // 마지막 점까지 확인해가면서 
			if(p[j].first < p[i].first + 1) { // p[j] >= p[i]+1이면 아래 계산 시간낭비임 
				for(int k = i+1; k <= j-1; k++) { // 안쪽으로 들어가는 '골'이 존재하는지 확인 
					//선분에서 O 점과 K점이 모두 선분으로 나누어지는 영역의 같은 영역에 속하는지 확인
					long long temp_o = ((long long)point[j].second-point[i].second)*((long long)X-point[i].first) - ((long long)point[j].first-point[i].first)*((long long)Y-point[i].second);
					long long temp_k = ((long long)point[j].second-point[i].second)*((long long)point[k].first-point[i].first) - ((long long)point[j].first-point[i].first)*((long long)point[k].second-point[i].second);
					//if( (point[i].first<point[k].first)&&(grad_ij>grad_ik) || (point[i].first>point[k].first)&&(grad_ij<grad_ik) ) { // point[i], poin[j], point[k] 끼리 비교해야 하는데 어떻게 비교해야 할까?? 
					if( (temp_o>0 && temp_k>0) || (temp_o<0 && temp_k<0) ) { // temp_k==0인건 직선 위에 있다는 뜻으로 틀린거. 
						double grad_i = ((double)Y-point[i].second)/(X-point[i].first);
						double grad_j = ((double)Y-point[j].second)/(X-point[j].first);
						double grad_k = ((double)Y-point[k].second)/(X-point[k].first);
						if(grad_i!=grad_k && grad_j!=grad_k) {
							p[j].first = p[i].first + 1;
							p_prev[j] = i;
							p[j].second.clear(); // 기존 정보 지워주고 업데이트 
							p[j].second.push_back( point[i] );
							p[j].second.push_back( point[k] );
							break;
						}
					}
				}
			}
		}
	}
	
	int maxi = -1, maxi_i = 0;
	for(int i = 0; i < point.size(); i++) {
		if(maxi < p[i].first) {
			maxi = p[i].first;
			maxi_i = i;
		}
	}
	if(p[maxi_i].first == 0) {
		cout << 0;
		return 0; 
	}
	else {
		cout << 2+(p[maxi_i].first*2) << '\n';
		cout << X << ' ' << Y << '\n';
		cout << point[maxi_i].first << ' ' << point[maxi_i].second << '\n';
		int cur = maxi_i;
		while(cur != -1) {
			if(!p[cur].second.empty()) {
				cout << p[cur].second[1].first << ' ' << p[cur].second[1].second << '\n';
				cout << p[cur].second[0].first << ' ' << p[cur].second[0].second << '\n';
			}
			cur = p_prev[cur];
		}
	}

	return 0;
}

Compilation message

footprint.cpp: In function 'int main()':
footprint.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < point.size(); i++) {
                 ~~^~~~~~~~~~~~~~
footprint.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < point.size()-2; i++) { // 처음 점부터 
                 ~~^~~~~~~~~~~~~~~~
footprint.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i+2; j < point.size(); j++) { // 마지막 점까지 확인해가면서 
                    ~~^~~~~~~~~~~~~~
footprint.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < point.size(); i++) {
                 ~~^~~~~~~~~~~~~~
footprint.cpp:34:19: warning: 'y_index' may be used uninitialized in this function [-Wmaybe-uninitialized]
  X = point[y_index].first; Y = point[y_index].second; // 뒤꿈치 좌표
                   ^

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 768 KB Output is correct
2 Correct 37 ms 640 KB Output is correct
3 Correct 52 ms 640 KB Output is correct
4 Correct 44 ms 640 KB Output is correct
5 Correct 40 ms 660 KB Output is correct
6 Correct 43 ms 640 KB Output is correct
7 Correct 37 ms 640 KB Output is correct
8 Correct 57 ms 648 KB Output is correct
9 Correct 44 ms 760 KB Output is correct
10 Correct 38 ms 640 KB Output is correct
11 Correct 37 ms 640 KB Output is correct
12 Correct 52 ms 640 KB Output is correct
13 Correct 46 ms 768 KB Output is correct
14 Correct 41 ms 640 KB Output is correct
15 Correct 38 ms 640 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 768 KB Output is correct
2 Correct 37 ms 640 KB Output is correct
3 Correct 52 ms 640 KB Output is correct
4 Correct 44 ms 640 KB Output is correct
5 Correct 40 ms 660 KB Output is correct
6 Correct 43 ms 640 KB Output is correct
7 Correct 37 ms 640 KB Output is correct
8 Correct 57 ms 648 KB Output is correct
9 Correct 44 ms 760 KB Output is correct
10 Correct 38 ms 640 KB Output is correct
11 Correct 37 ms 640 KB Output is correct
12 Correct 52 ms 640 KB Output is correct
13 Correct 46 ms 768 KB Output is correct
14 Correct 41 ms 640 KB Output is correct
15 Correct 38 ms 640 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Incorrect 3 ms 384 KB Output isn't correct
20 Halted 0 ms 0 KB -