Submission #96936

#	Time	Username	Problem	Language	Result	Execution time	Memory
96936		kyn01286	공룡 발자국 (KOI18_footprint)	C++14	14 / 100	57 ms	768 KiB

footprint

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

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 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45