?? 2007 jarvis march.cpp
字號:
// a package wrappint technology
// O(nh) h 為凸包上的頂點數(shù) creat by jarvis
#include"iostream"
#include"stdio.h"
#include"math.h"
#include"stdlib.h"
#include"algorithm"
using namespace std;
#define N 64
#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];
point Q[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));
}
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;
}
bool 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;
}
point u = min; k = 0;
while(u != max) {
point v = min_polar_angle(u,_right);
u = v; Q[k++] = v;
//printf("(%.1lf,%.1lf)\n",v.x,v.y);
}
while(u != min) {
point v = min_polar_angle(u,_left);
u = v; Q[k++] = v;
//printf("(%.1lf,%.1lf)\n",v.x,v.y);
}
return true;
}
void change()
{ int i;
for(i = 0; i < n; i++)
if(!(Q[i] != P[0])) break;
int j = i;
do {
printf("(%.0lf,%.0lf)\n",Q[j].x,Q[j].y);
}while(j != i);
}
void input()
{
int i = 0;
while(scanf("%lf%lf",&P[i].x,&P[i].y) != EOF) i++;
n = i;
}
int main()
{
//freopen("in.txt","r",stdin);
input();
convex_hull();
change();
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -