ECNU 1624 교차 다각형 면적 구하 기

9655 단어
사실 저 는 hdu 3060 을 하고 싶 은 데...쓰 고 보 니...이 문제 갱 언니, 그리고 오목 한 상황...어 쩔 수 없 이 OJ 를 찾 아서 두 개의 돌출 된 코드 를 건 네 주 었 다.
두 개의 돌출 다각형 면적 을 구하 다.물 문제 야.물 을 넘 길 수 있 는 방법 을 생각 했 는데.계속 WA.나중에 반 평면 으로 내 면 되 는데...오 랜 만 에 반 평면 으로 낸 문 제 를...
방금 버그 를 고 쳤 어 요. 제 방법 도 지 나 갔 어 요!!(* ^ ^ *) 히히...
나 는 M * N 의 알고리즘 이 고 반 평면 교 류 는 log (N + M) * (N + M) 의 것 이다.
저 는 이것 이 너무 보고 싶 습 니 다. 면적 의 교 제 를 구 하 는 이상 돌출 다각형 이기 때문에 두 개의 교 집합 도 반드시 돌출 되 어 있 을 것 입 니 다 (존재 한다 면).
그리고 조금 만 생각해 보면 알 수 있 듯 이 돌출 다각형 의 정점 은 교점 이거 나 다른 돌출 다각형 에 있 는 점 이다.그래서 이 점 들 을 하나의 집합 에 넣 고 극 각 정렬 을 한 다음 에 면적 을 구하 면 됩 니 다 ~ ~ 하 나 를 완전히 포함 하 는 지, 그리고 내 고 싶 지 않 은 지 여 부 를 특별히 판단 해 야 합 니 다 ~
중간 에 WA 는 구 하 는 점 집 이 포인트 가 있 으 면 극 각 으로 정렬 (atan 2 로) 하 는 것 은 믿 을 수 없 기 때 문 입 니 다!!같은 점 을 가 진 atan 2 의 결 과 는 0 이기 때문이다!한편, 극 각 순 서 는 마이너스 에서 플러스 까지 이다. 만약 에 두 점 이 같 으 면 극 각 순 서 를 거 친 후에 두 사람 은 함께 있 지 않 고 울 었 다.그래서 극 각 정렬 전에 다시 내 리 는 것 은 문제 가 없다.
개선 공간 이 많 습 니 다.
나의 N * M 방법
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)

using namespace std;

const int MAX = 510;

const double eps = 1e-6;
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
struct point{
	double x, y;
	void get()
	{
		scanf("%lf%lf", &x, &y);
	}
	bool operator==(const point &a)
	{
		return dd(a.x, x) && dd(a.y, y);
	}
};

double crossProduct(point a,point b,point c)//   ac   ab           
{
	return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
}
point l2l_inst_p(point u1,point u2,point v1,point v2)
{
	point ans = u1;
	double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x))/
				((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x));
	ans.x += (u2.x - u1.x)*t;
	ans.y += (u2.y - u1.y)*t;
	return ans;
}
bool onSegment(point a, point b, point c)
{
	if( dd(crossProduct(a,b,c),0.0) && dyd(c.x,min(a.x,b.x)) && 
		xyd(c.x,max(a.x,b.x)) && dyd(c.y,min(a.y,b.y)) && xyd(c.y,max(a.y,b.y)) )
		return true;
	return false;
}
bool s2s_inst(point p1,point p2, point p3, point p4) 
{
	double d1 = crossProduct(p3,p4,p1);
	double d2 = crossProduct(p3,p4,p2);
	double d3 = crossProduct(p1,p2,p3);
	double d4 = crossProduct(p1,p2,p4);
	if( xy(d1 * d2, 0.0) && xy(d3 * d4, 0.0) ) return true;		
	return false;
}
point p1[MAX], p2[MAX];
bool pin_convexh(point *p,int n,point a)
{
	p[n] = p[0]; p[n+1] = p[1];
	for(int i=0; i<n; i++)
		if( xy(crossProduct(p[i],p[i+1],a)*
			crossProduct(p[i+1],p[i+2],a),0.0) )
			return false;
	return true;
} 
double area_polygon(point p[],int n)
{
	if( n < 3 ) return 0.0; 
	double s = 0.0;
	for(int i=0; i<n; i++)
		s += p[(i+1)%n].y * p[i].x - p[(i+1)%n].x * p[i].y;
	return fabs(s)/2.0;
}
bool ainb(point *a, int n, point *b, int m)
{
	FOR(i, 0, n)
		if( !pin_convexh(b, m, a[i]) )
			return false;
	return true;
}
bool inst(point *a, int n, point *b, int m)
{
	FOR(i, 0, n)
		FOR(k, 0, m)
			if( s2s_inst(a[i], a[i+1], b[k], b[k+1]) )
				return true;
	return false;
}
	
point t[MAX*2], C;
bool cmp(point a,point b)  
{  
	double t1 = atan2(a.y - C.y, a.x - C.x);
	double t2 = atan2(b.y - C.y, b.x - C.x);
    if( dd(t1, t2) ) return xy(fabs(a.x),fabs(b.x));
    return xy(t1, t2);  
}
bool cmp_p(point a, point b)
{
	if( dd(a.x, b.x) )
		return xy(a.y, b.y);
	return xy(a.x, b.x);
}
bool cmp_equal(point a, point b)
{
	return a == b;
}

double solve(int n, int m)
{
	double area1 = area_polygon(p1, n);
	double area2 = area_polygon(p2, m);
	if( ainb(p1, n, p2, m) || ainb(p2, m, p1, n) )	//           ，         
		return min(area1, area2);
	if( !inst(p1, n, p2, m) )		//        
		return 0;
									//       ，   
	int cnt = 0;
	FOR(i, 0, n)
		FOR(k, 0, m)
			if( s2s_inst(p1[i], p1[i+1], p2[k], p2[k+1]) )
				t[cnt++] = l2l_inst_p(p1[i], p1[i+1], p2[k], p2[k+1]);
				
	FOR(i, 0, n)
		if( pin_convexh(p2, m, p1[i]) )
			t[cnt++] = p1[i];
	
	FOR(i, 0, m)
		if( pin_convexh(p1, n, p2[i]) )
			t[cnt++] = p2[i];
	
	sort(t, t+cnt, cmp_p);
	cnt = unique(t, t+cnt, cmp_equal) - t;
	C = t[0];
	sort(t+1, t+cnt, cmp);
	cnt = unique(t, t+cnt, cmp_equal) - t;
	double area = area_polygon(t, cnt);
	return area;
} 
	
int main()
{
	int n, m;
	
	while( ~scanf("%d", &n) )
	{
		FOR(i, 0, n)
			p1[i].get();
		
		scanf("%d", &m);
		FOR(i, 0, m)
			p2[i].get();
		
		p1[n] = p1[0]; p2[m] = p2[0];
		double ans = solve(n, m);
		printf("%.2lf
", ans);
	}

return 0;
}

반 평면 교차 방법
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)

using namespace std;

const int MAX = 510;

const double eps = 1e-8;
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
struct point{
	double x, y;
	void get()
	{
		scanf("%lf%lf", &x, &y);
	}
	bool operator==(const point &a)
	{
		return dd(a.x, x) && dd(a.y, y);
	}
};

double crossProduct(point a,point b,point c)//   ac   ab           
{
	return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
}
double area_polygon(point p[],int n)
{
	if( n < 3 ) return 0.0; 
	double s = 0.0;
	for(int i=0; i<n; i++)
		s += p[(i+1)%n].y * p[i].x - p[(i+1)%n].x * p[i].y;
	return fabs(s)/2.0;
}
	
point t[MAX*2], p1[MAX], p2[MAX];
struct line{
	point a, b;
	double ang;
};
line ln[MAX*2], deq[MAX*2];
bool cmp_equal(point a, point b)
{
	return a == b;
}
bool equal_ang(line a,line b)	//    unique      
{
	return dd(a.ang, b.ang);
}
bool cmphp(line a,line b)	//         
{
	if( dd(a.ang,b.ang) ) return xy(crossProduct(b.a,b.b,a.a),0.0);
	return xy(a.ang,b.ang);
}
bool equal_p(point a,point b)//   unique      
{
	return dd(a.x,b.x) && dd(a.y,b.y);
}
void makeline_hp(double x1,double y1,double x2,double y2,line &l)
{
	l.a.x = x1; l.a.y = y1; l.b.x = x2; l.b.y = y2;
	l.ang = atan2(y2 - y1,x2 - x1);
}
void makeline_hp(point a,point b,line &l) //   (  ab)        
{
	l.a = a; l.b = b;
	l.ang = atan2(b.y - a.y,b.x - a.x);	//        ，  a.y - b.y,a.x - b.x 
}
bool parallel(line u,line v)
{
	return dd( (u.a.x - u.b.x)*(v.a.y - v.b.y) - (v.a.x - v.b.x)*(u.a.y - u.b.y) , 0.0 );
}
point l2l_inst_p(line l1,line l2)
{
	point ans = l1.a;
	double t = ((l1.a.x - l2.a.x)*(l2.a.y - l2.b.y) - (l1.a.y - l2.a.y)*(l2.a.x - l2.b.x))/
			   ((l1.a.x - l1.b.x)*(l2.a.y - l2.b.y) - (l1.a.y - l1.b.y)*(l2.a.x - l2.b.x));
	ans.x += (l1.b.x - l1.a.x)*t;
	ans.y += (l1.b.y - l1.a.y)*t;
	return ans;
}
void inst_hp_nlogn(line *ln,int n,point *s,int &len)
{
	len = 0;
	sort(ln,ln+n,cmphp);
	n = unique(ln,ln+n,equal_ang) - ln;
	int bot = 0,top = 1;
	deq[0] = ln[0]; deq[1] = ln[1];
	for(int i=2; i<n; i++)
	{
		if( parallel(deq[top],deq[top-1]) || parallel(deq[bot],deq[bot+1]) )
			return ;
		while( bot < top && dy(crossProduct(ln[i].a,ln[i].b,
			l2l_inst_p(deq[top],deq[top-1])),0.0) )
			top--;
		while( bot < top && dy(crossProduct(ln[i].a,ln[i].b,
			l2l_inst_p(deq[bot],deq[bot+1])),0.0) )
			bot++;
		deq[++top] = ln[i];
	}
	while( bot < top && dy(crossProduct(deq[bot].a,deq[bot].b,
		l2l_inst_p(deq[top],deq[top-1])),0.0) )	top--;
	while( bot < top && dy(crossProduct(deq[top].a,deq[top].b,
		l2l_inst_p(deq[bot],deq[bot+1])),0.0) )	bot++;
	if( top <= bot + 1 ) return ;
	
	for(int i=bot; i<top; i++)
		s[len++] = l2l_inst_p(deq[i],deq[i+1]);
	if( bot < top + 1 ) s[len++] = l2l_inst_p(deq[bot],deq[top]);
	len = unique(s,s+len,equal_p) - s;
} 

double solve(int n, int m)
{
	int cnt = 0;
	FOR(i, 0, n)
		makeline_hp(p1[i], p1[i+1], ln[cnt++]);
	FOR(i, 0, m)
		makeline_hp(p2[i], p2[i+1], ln[cnt++]);
	
	int len;
	inst_hp_nlogn(ln, cnt, t, len);
	if( len == 0 ) return 0;
	
	double area = area_polygon(t, len);
	return area;
} 
	
int main()
{
	int n, m;
	
	while( ~scanf("%d", &n) )
	{
		for(int i=n-1; i>=0; i--)
			p1[i].get();
		
		scanf("%d", &m);
		for(int i=m-1; i>=0; i--)
			p2[i].get();
		
		p1[n] = p1[0]; p2[m] = p2[0];
		double ans = solve(n, m);
		printf("%.2lf
", ans);
	}

return 0;
}
useComponent 패턴 소개
흔 한 비트 연산 기법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage