文章

1

粉丝

66

获赞

2

访问

4.0k

头像
凸包面积的解题思路
P1113
发布于2022年6月6日 16:55
阅读数 4.0k

#include<iostream>
#include<cmath>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct{
	int x,y;
}Coor;
Coor a[5000];
double area;
double Area(int p1, int p2, int p3){
	 return 0.5*fabs((a[p2].x -a[p1].x )*(a[p3].y - a[p2].y ) - (a[p3].x - a[p2].x )*(a[p2].y - a[p1].y ));
}
//判断位置,小于零,逆,反之则顺 
bool pos( int p1,int p2, int p3){
	int m = ((a[p2].x -a[p1].x )*(a[p3].y - a[p2].y));
	if(m > 0) return true;
	return false;
}
void convex_hull(bool pos1, int p1, int p2){
	int p = -1;
	double area_max = -1.0;
	for(int i = p1+1; i < p2 ;i++){
		if( pos1 == pos(p1, p2, i) ) continue;
		if(Area(p1, p2, i) > area_max ){
			area_max = Area(p1, p2, i);
			p = i;
		}
	}
	if( p == -1) return ;
	area += area_max;
	convex_hull( pos1, p1, p);
	convex_hull( pos1, p, p2);
}
bool cmp(Coor p1, Coor p2){
	return p1.x  < p2.x  ;
}
int main(){
	int n,m;
	cin>>n;
	while(n>0){
		cin>>m;
		area = 0...
登录查看完整内容


登录后发布评论

1 条评论
yanchi VIP
2023年3月29日 14:50

pos函数里面的m应该等于((a[p2].x -a[p1].x )*(a[p3].y - a[p2].y)- (a[p3].x - a[p2].x )*(a[p2].y - a[p1].y )),这样才能判断p3在p1p2这条线的顺时针和逆时针

赞(0)