글 읽기 - 1077 넓이 질문입니다

portableangel 8년 전 0

1. 도형 A 내부(경계선 포함)에 있는 도형 B의 꼭지점

2. 도형 B 내부(경계선 포함)에 있는 도형 A의 꼭지점

3. 도형 A와 도형 B가 교차하는 점

을 뽑고, 얘네로 컨벡스를 만든 후 삼각분할로 넓이를 구하는 코드입니다.

라운딩 에러인지, 알고리즘에 문제가 있는지 궁금합니다.

또 문제 입력 예제에 테스트케이스가 두 개인데, 출력은 하나만 있습니다. 아마 누락 같습니다.

#include <stdio.h>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAX 1000000000.0

class p {
public:
	double x, y;
	double r;
	p(double x, double y)
		:x(x),y(y),r(0.0)
	{}
};

int ccw(p& a, p& b, p& c) {
	double d=a.x*b.y+b.x*c.y+c.x*a.y-(a.x*c.y+b.x*a.y+c.x*b.y);
	if(d>0) return 1;
	else if(d<0) return -1;
	return 0;
}

bool cmp1(const p &i, const p &j) {
	if(i.y!=j.y) return i.y<j.y;
	else return i.x<j.x;
}

bool cmp(const p &i, const p &j) {
	if(i.r!=j.r) return i.r<j.r;
	else if(i.x!=j.x) return i.x<j.x;
	else return i.y<j.y;
}

double s(p& a, p& b, p& c) {
	double ret=(a.x*b.y+b.x*c.y+c.x*a.y)-(b.x*a.y+c.x*b.y+a.x*c.y);
	if(ret<0) ret=-ret;
	return ret;
}

double scon(vector<p>& arr) {
	if(arr.size()<3) return 0;
	double ret=0;
	for(int i=1;i<arr.size()-1;i++) {
		ret+=s(arr[0],arr[i],arr[i+1]);
	}
	return ret;
}

void getinter(vector<p>& arr, p& a, p& b, p& c, p& d) {
	double xi, yi;
	if(ccw(a,b,c)*ccw(a,b,d)<0 && ccw(c,d,a)*ccw(c,d,b)<0) {
		if(a.x==b.x) {
			xi=a.x;
			yi=(d.y-c.y)/(d.x-c.x)*(xi-c.x)+c.y;
			arr.push_back(p(xi,yi));
		} else if(c.x==d.x) {
			xi=c.x;
			yi=(b.y-a.y)/(b.x-a.x)*(xi-a.x)+a.y;
			arr.push_back(p(xi,yi));
		} else {
			double m1=(b.y-a.y)/(b.x-a.x);
			double m2=(d.y-c.y)/(d.x-c.x);
			xi=((m1*a.x-a.y)-(m2*c.x-c.y))/(m1-m2);
			yi=m1*xi-m1*a.x+a.y;
			arr.push_back(p(xi,yi));
		}
	}
}

int main() {
	int n, m;
	while(~scanf("%d %d",&n,&m)) {
		vector<p> s1, s2;
		for(int i=0;i<n;i++) {
			double x, y;
			scanf("%lf %lf",&x,&y);
			s1.push_back(p(x,y));
		}
		for(int i=0;i<m;i++) {
			double x, y;
			scanf("%lf %lf",&x,&y);
			s2.push_back(p(x,y));
		}
		s1.push_back(s1[0]);
		s2.push_back(s2[0]);
		vector<p> inter;
		for(int i=0;i<s1.size()-1;i++) {
			bool ok=true;
			for(int j=0;j<s2.size()-1;j++) {
				if(ccw(s2[j],s2[j+1],s1[i])<0) {
					ok=false;
					break;
				}
			}
			if(ok) inter.push_back(s1[i]);
		}
		for(int i=0;i<s2.size()-1;i++) {
			bool ok=true;
			for(int j=0;j<s1.size()-1;j++) {
				if(ccw(s1[j],s1[j+1],s2[i])<0) {
					ok=false;
					break;
				}
			}
			if(ok) inter.push_back(s2[i]);
		}
		for(int i=0;i<s1.size()-1;i++) {
			for(int j=0;j<s2.size()-1;j++) {
				getinter(inter,s1[i],s1[i+1],s2[j],s2[j+1]);
			}
		}
		if(inter.size()<3) {
			printf("%.10f\n",0.0);
			continue;
		}
		sort(inter.begin(),inter.end(),cmp1);
		inter[0].r=-1.0;
		for(int i=1;i<inter.size();i++) {
			if(inter[i].x==inter[0].x) inter[i].r=MAX;
			else {
				inter[i].r=1.0*(inter[i].y-inter[0].y)/(inter[i].x-inter[0].x);
				if(inter[i].r<0) inter[i].r+=2.0*MAX;
			}
		}
		sort(inter.begin(),inter.end(),cmp);
		vector<p> intercon;
		intercon.push_back(inter[0]);
		intercon.push_back(inter[1]);
		for(int i=2;i<inter.size();i++) {
			while(intercon.size()>=2 && ccw(intercon[intercon.size()-2],intercon.back(),inter[i])<=0)
				intercon.pop_back();
			intercon.push_back(inter[i]);
		}
		double res=scon(intercon);
		printf("%.10f\n",res/2.0);
	}
}

baekjoon 8년 전 0

ㅇㅖ제 하나 지웠습니다

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

문제

문제

출처

ICPC

1077 넓이 질문입니다

portableangel 8년 전 0

baekjoon 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말