제출 #131075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131075		sean617	곡선 자르기 (KOI17_cut)	C++98	100 / 100	395 ms	36472 KiB

cut

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1000005
#define F first
#define S second
using namespace std;

int n, sz, st, m, cnt, s1, s2, mx, mn = 2e9, rs, x[N], y[N], a[N];
struct str {
	int c, z, num;
} b[N];

bool comp(str p, str q) {
	return p.c < q.c;
}
int main()
{
	int i, j;
	cin >> n;
	sz = st = 1;
	for (i = 0; i < n; i++) {
		scanf ("%d %d", &x[i], &y[i]);
		if (x[i] < mn) {
			mn = x[i];
			rs = i;
		}
	}
	for (j = 0, i = rs; j < n; j++, i = (i + 1) % n) {
		if (y[i] > 0 && y[(i - 1 + n) % n] < 0 || y[i] < 0 && y[(i - 1 + n) % n] > 0) a[sz++] = x[i];
	}
	if (y[rs] > 0) {
		st = 0;
		a[0] = a[sz - 1];
		sz--;
	}
	for (i = st, j = 1; i < sz; i += 2, j++) {
		if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);
		b[m].c = a[i];
		b[m + 1].c = a[i + 1];
		b[m].z = 1;
		b[m + 1].z = 2;
		b[m].num = j;
		b[m + 1].num = j;
		m += 2;
	}
	sort(b, b + m, comp);
	mx = -2e9;
	for (i = 0; i < m; i++) {
		if (b[i].z == 1) {
			cnt++;
			if (cnt == 1) s1++;
			if (b[i + 1].z == 2 && b[i + 1].num == b[i].num) s2++;
		} else cnt--;
	}
	cout << s1 << " " << s2;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cut.cpp: In function 'int main()':
cut.cpp:30:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if (y[i] > 0 && y[(i - 1 + n) % n] < 0 || y[i] < 0 && y[(i - 1 + n) % n] > 0) a[sz++] = x[i];
       ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cut.cpp:23:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d", &x[i], &y[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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