글 읽기 - 44%에서 계속 틀립니다...

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

44%에서 계속 틀립니다...

7420번 - 맹독 방벽

system_error_code_0 2년 전 0

다른 컨벡스 헐 문제는 잘 풀리는데

이 문제만 실수 오차 문제인 것인가

몇 번을 오차를 잡으려고 해도

계속 44%에서 틀리다고 하네요....

질문 게시판에 있는 내용도 참고했지만

해결 방법이 되지 않았네요

제가 놓치고 있는 문제점이 있을까요?

#include <iostream>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
using namespace std;
struct D{
	long long x,y;
};
D d[1010],mi={99999,99999},s[1010];
long long ccw(D a,D b,D c) {
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(D a,D b) {
	long long n=ccw(d[0],a,b);
	if(n==0) return (abs(a.x)+abs(a.y))<(abs(b.x)+abs(b.y));
	if(n>0) return 1;
	return 0;
}
double dist(D a,D b) {
	double n=double((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
	return sqrt(n);
}
int main() {
	int n,idx,l;
	cin>>n>>l;
	for(int i=0;i<n;i++) {
		scanf("%lld %lld",&d[i].x,&d[i].y);
		if(d[i].y<mi.y||(d[i].y==mi.y&&d[i].x<mi.x)) {
			mi={d[i].x,d[i].y};
			idx=i;
		}
	}
	swap(d[0],d[idx]);
	sort(d+1,d+n,cmp);
	s[0]=d[0];
	s[1]=d[1];
	idx=2;
	for(int i=2;i<n;i++) {
		while(idx>1&&ccw(s[idx-2],s[idx-1],d[i])<=0) idx--;
		s[idx++]=d[i];
	}
	double r=0;
	for(int i=1;i<idx;i++) {
		r+=dist(s[i-1],s[i]);
	}
	r+=dist(s[0],s[idx-1])+(double)2*(double)l*M_PI;
	cout<<round(r);
}

kwakws0627 2년 전 1

안녕하세요, 반례 드릴게요

cmp 함수 구현이 조금 꼬인거 같네요

input
3 1
-10 -10
-2 -2
1 1
wrong output
29
ans
37

system_error_code_0 2년 전 1

아... cmp 내 n==0일 때 기준점 d[0]을 원점으로 잡고(=평행이동) 절댓값을 계산 했어야 했는데

그것을 빼먹은 걸 미처 생각하지 못했습니다ᅮ

빠르고 정확한 답변 정말 감사드립니다.

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

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

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

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

한국어 | English (Beta)

문제

문제

출처

ICPC