1113 jarvis march.cpp

各种算法

// a package wrappint technology
// O(nh) h 为凸包上的顶点数 creat by jarvis
#include"iostream"
#include"stdio.h"
#include"math.h"
#include"stdlib.h"
#include"algorithm"
using namespace std;
#define N 1024
#define INF (unsigned int)(-1)>>1
#define PI 3.1415926
enum orientation{ _left = -1,straight = 0,_right = 1};

typedef struct point{
	double x;
	double y;
	//double z;
	point(){}
	point(double a,double b){x = a; y = b;}
	point operator <(point a)
	{
		if(y < a.y) return (point &)*this;
		else return a;
	}
	point operator >(point a)
	{
		if(y > a.y) return (point &)*this;
		else return a;
	}
	bool operator !=(point a)
	{
		if(x != a.x || y != a.y) return true;
		else return false;
	}
}point;
point P[N];
int n,r;
int check[N] = {0};


double cross(point a,point b,point c)//Cross product  叉积
{	
	point m(b.x - a.x,b.y - a.y);
	point n(c.x - a.x,c.y - a.y);
	return m.x*n.y - m.y*n.x;
}
double length(point p,point q)
{	return sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2));
}
bool input()
{	
	if(scanf("%d%d",&n,&r) != 2) return false;
	for(int i = 0;i < n;i++) scanf("%lf%lf",&P[i].x,&P[i].y);
	return true;
}
struct point MAKE_VECTOR (point u,point v)
{
	return point(v.x - u.x,v.y - u.y);
}

struct point min_polar_angle(point u,int orient)
{
	point v; int k = N-1; int j;
	for (j = 0; j < n; j++)
		if(check[j] == orient) { v = P[j]; k = j; break; }
	for (int i = j+1; i < n; i++) 
		if (check[i] == orient) {
			double direct = cross(u,v,P[i]); 
			if((direct == 0 && length(u,v) < length(u,P[i])) || direct < 0)
			{ v = P[i]; k = i; }
		}
	check[k] = false;
	return v;
}
double convex_hull()
{	
	point min(INF,INF),max(-INF,-INF);
	int i = 0,j,k;
	for(i = 0; i < n; i++) {
		if(min != min<P[i]) { min = P[i]; j = i; }
		if(max != max>P[i]) { max = P[i]; k = i; }
	}
	check[j] = _left; check[k] = _right;;	
	for(i = 0; i < n; i++) {
		double direct = cross(min,max,P[i]);
		if(direct < 0)	check[i] = _right;
		else if(direct > 0) check[i] = _left;	
	}
	double sum = PI * 2 * r;
	point u = min;
	while(u != max) {
		point v = min_polar_angle(u,_right);
		sum += length(u,v);
		u = v; 
		//printf("(%.1lf,%.1lf)\n",v.x,v.y);
	}
	while(u != min) {
		point v = min_polar_angle(u,_left);
		sum += length(u,v);
		u = v;
		//printf("(%.1lf,%.1lf)\n",v.x,v.y);
	}
	return sum;
}

int main()
{
	//freopen("in.txt","r",stdin);
	while(input()){
		printf("%.0lf\n",convex_hull());
	}
	return 0;
}