文章
1
粉丝
66
获赞
2
访问
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...
登录后发布评论
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这条线的顺时针和逆时针