글 읽기 - 틀렸는데 왜 틀렸는지 모르겠습니당 ㅠㅠ(모노톤 알고리즘)

vl0612 4년 전 0

Monotone()으로 컨벡스헐을 구하고 ccw_forCircle()함수로 직선 경로 및 곡선경로를 구했습니다.

반례도 안 보이고 변수형 때문에 틀렸나 싶었지만 그것두 아닌 것 같구(<-아래처럼 long long int와 long double로 바꿔서 제출했는데 그래도 틀 .. ㅠㅠ

#include<bits/stdc++.h>
#define ll long long
#define double long double
using namespace std;
int N; ll L;
struct point{ ll int y,x; }Point[2000];
bool cmp_x_y(point a, point s){ if(a.x==s.x) return a.y<s.y; return a.x<s.x; }
deque<point> convex_hull;
int ccw(point a, point b, point c){
	ll int ret=(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
	if(ret>0) return -1; else if(ret==0) return 0; else return 1;
}// 1 counter-clockwise -1 clockwise
double ccw_forCircle(point a,point b,point c){ //a-b직선경로와 abc 곡선경로 반환 
	double ret=(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
	if(ret<0) ret=-ret;
	ret/=(double)sqrt((double)pow(b.y-a.y,2)+pow(b.x-a.x,2));
	ret/=(double)sqrt((double)pow(c.y-b.y,2)+pow(c.x-b.x,2));
	ret=(double)asin(ret);
	ret=(double)L*ret;
	return ret+(double)sqrt((double)pow(b.y-a.y,2)+pow(b.x-a.x,2));
}
void Monotone(){
	deque<point> up_hull,down_hull;
	int sz=0;
	for(int i=1;i<=N;i++){
		while(sz>=2 && ccw(up_hull[sz-2],up_hull[sz-1],Point[i])<=0) sz--, up_hull.pop_back();
		up_hull.push_back(Point[i]); sz++;
	}
	sz=0;
	for(int i=N;i>=1;i--){
		while(sz>=2 && ccw(down_hull[sz-2],down_hull[sz-1],Point[i])<=0) sz--, down_hull.pop_back();
		down_hull.push_back(Point[i]); sz++;
	}
	sz=up_hull.size();
	for(int i=0;i<sz;i++) convex_hull.push_back(up_hull[i]);
	sz=down_hull.size();
	for(int i=sz-2;i>=1;i--) convex_hull.push_back(down_hull[i]);
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>N>>L;
	ll ix,iy;
	for(int i=1;i<=N;i++){
		cin>>ix>>iy;
		Point[i].y=iy; Point[i].x=ix;
	}
	sort(Point+1,Point+1+N,cmp_x_y);
	Monotone();
	double ans=0;
	int sz=convex_hull.size();
	if(sz==2){
		ans=2*3.14159265358979*L+2*(double)sqrt((double)pow(convex_hull[1].y-convex_hull[0].y,2)+pow(convex_hull[1].x-convex_hull[0].x,2));
	}
	else {
		for(int i=0;i<sz;i++){
			ans+=ccw_forCircle(convex_hull[(i-1+sz)%sz],convex_hull[i],convex_hull[(i+1)%sz]);
		}
	}
	cout<<round(ans);
}

vl0612 4년 전 0

결국 던지고 다시 짜는 걸(?!!!)로 해결했습니다

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

문제

문제

출처

ICPC

틀렸는데 왜 틀렸는지 모르겠습니당 ㅠㅠ(모노톤 알고리즘)

vl0612 4년 전 0

vl0612 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말