글 읽기 - 100%에서 틀렸습니다...

(追記) (追記ここまで)

100%에서 틀렸습니다...

7420번 - 맹독 방벽

ness9917 3년 전 1

컨벡스 헐 구한다음에 원의 둘레 더해서 풀었는데 어디가 틀렸는지 모르겠어요..

반례 부탁드립니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <map>
#include <stack>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long long ld;
typedef tuple<ll, ll, ll, ll> tiiii;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pdd;
#define X first
#define Y second
long double PI = acos(-1);
pdd pivot;
ld cross(pdd a, pdd b) {
	return a.X * b.Y - a.Y * b.X;
}
pdd subt(pdd a, pdd b) {
	return { b.X - a.X, b.Y - a.Y };
}
ld pabs2(pdd a) {
	return (a.X - pivot.X) * (a.X - pivot.X) + (a.Y - pivot.Y) * (a.Y - pivot.Y);
}
bool compy(pdd a, pdd b) {
	if (a.Y == b.Y) {
		return a.X < b.X;
	}
	return a.Y < b.Y;
}
bool compa(pdd a, pdd b) {
	ld crs = cross(subt(pivot, a), subt(pivot, b));
	if (crs == 0) {
		return pabs2(a) < pabs2(b);
	}
	return crs > 0;
}
pdd second(stack<pdd>& s) {
	pdd temp = s.top();
	s.pop();
	pdd sec = s.top();
	s.push(temp);
	return sec;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	ld len;
	cin >> n >> len;
	vector<pdd> vec;
	for (int i = 1; i <= n; i++) {
		ld x, y;
		cin >> x >> y;
		vec.push_back({ x, y });
	}
	sort(vec.begin(), vec.end(), compy);
	pivot = vec[0];
	vec.erase(vec.begin());
	sort(vec.begin(), vec.end(), compa);
	vec.push_back(pivot);
	stack <pdd> s;
	s.push(pivot);
	s.push(vec[0]);
	for (int i = 1; i < vec.size(); i++) {
		ld crs = cross(subt(s.top(), second(s)), subt(vec[i], s.top()));
		while (crs < 0) {
			s.pop();
			crs = cross(subt(s.top(), second(s)), subt(vec[i], s.top()));
		}
		if (crs == 0) {
			s.pop();
		}
		s.push(vec[i]);
	}
	long double sum = 0;
	pdd prev = s.top();
	s.pop();
	pdd tp;
	while (!s.empty()) {
		tp = s.top();
		s.pop();
		pdd st = subt(tp, prev);
		sum += sqrt((double)(st.X*st.X + st.Y*st.Y));
		prev = tp;
	}
	cout << fixed;
	cout.precision(0);
	cout << sum + 2 * PI * len;
	return 0;
}

kwakws0627 3년 전 2

반례 입니다.

모든 도시들이 한 직선 위에 있을 때 이상한 답을 내고 있네요

(저도 100% 에서 계속 '틀렸습니다' 나오다가 이 반례 처리하니까 '정딥입니다' 나왔습니다.)

// input
10 1
4 4
8 8
2 2
9 9
0 0
10 10
1 1
3 3
7 7
5 5
// wrong
6
// answer
35

ness9917 3년 전 0

감사합니다~

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC