Submission #200419

#	Time	Username	Problem	Language	Result	Execution time	Memory
200419		wjdqhdhfflavldkem12	곡선 자르기 (KOI17_cut)	C++14	100 / 100	436 ms	24132 KiB

cut

#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#include <limits.h>

using namespace std;

#define LEFT 0
#define RIGHT 1
#define node pair<int, bool>

int n, inPeak, outPeak;
vector<node> LIST;

bool compare(node a, node b){
	return a.first < b.first;
}

int main(){
	int i;

	/*변수입력*/
	//꼭짓점의 개수 입력
	scanf("%d", &n);
	//각 꼭짓점의 x, y좌표 입력 & 가장 왼쪽에 있는 수직선분의 두 점 중 아래의 점으로 시작지점으로 지정할 점을 찾는다.
	int xtemp, ytemp, start;
	int minx = INT_MAX, miny = INT_MAX;
	vector<int> x, y;
	for (i = 0; i < n; i++){
		scanf("%d %d", &xtemp, &ytemp);
		x.push_back(xtemp);
		y.push_back(ytemp);
		if (ytemp <= miny && xtemp <= minx){
			start = i;
			minx = xtemp; miny = ytemp;
		}
	}
	// 시작지점 이전의 점들을 시작지점 이후로 옮겨 붙인다.
	for (i = 0; i < start; i++){
		x.push_back(x[i]);
		y.push_back(y[i]);
	}

	/*봉우리의 시작 기둥과 끝기둥을 찾아 입력한다.*/
	//두 개의 기둥을 왼쪽 기둥과 오른쪽 기둥으로 구분하여 입력한다.
	int size = 0;
	pair<int, int> temp;
	for (i = start; i < n+start-1; i++){
		if (y[i]<0 && y[i + 1]>0){
			size++;
			temp.first = i;
		}
		else if (y[i]>0 && y[i + 1] < 0){
			size++;
			temp.second = i;
			if (x[temp.first] < x[temp.second]){
				LIST.push_back(node(x[temp.first], LEFT));
				LIST.push_back(node(x[temp.second], RIGHT));
			}
			else{
				LIST.push_back(node(x[temp.first], RIGHT));
				LIST.push_back(node(x[temp.second], LEFT));
			}
		}
	}

	/*입력된 기둥을 x좌표를 기준으로 오름차순 정렬한다.*/
	sort(LIST.begin(), LIST.end(), compare);
	
	/*기둥의 배치를 이용하여 원하는 봉우리의 개수를 찾는다.*/
	int count = 0;
	for (i = 0; i < size; i++){
		if (LIST[i].second == LEFT){
			count++;
			if (count == 1)
				outPeak++;
		}
		else{
			count--;
			if (LIST[i - 1].second == LEFT)
				inPeak++;
		}
	}

	/*표준출력에 맞추어 출력한다.*/
	printf("%d %d\n", outPeak, inPeak);


	return 0;
}

Compilation message (stderr)

cut.cpp: In function 'int main()':
cut.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
cut.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &xtemp, &ytemp);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cut.cpp:27:20: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int xtemp, ytemp, start;
                    ^~~~~

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 65 / 65