圈水池 nyoj 78 凸包算法

圈水池

时间限制：3000 ms | 内存限制：65535 KB

难度：4

描述: 有一个牧场，牧场上有很多个供水装置，现在牧场的主人想要用篱笆把这些供水装置圈起来，以防止不是自己的牲畜来喝水，各个水池都标有各自的坐标，现在要你写一个程序利用最短的篱笆将这些供水装置圈起来！（篱笆足够多，并且长度可变）

输入

第一行输入的是N,代表用N组测试数据（1<=N<=10）
第二行输入的是m,代表本组测试数据共有m个供水装置（3<=m<=100）
接下来m行代表的是各个供水装置的横纵坐标

输出

输出各个篱笆经过各个供水装置的坐标点，并且按照x轴坐标值从小到大输出，如果x轴坐标值相同，再安照y轴坐标值从小到大输出

样例输入

样例输出

0 0

2 3

3 0

该题可用于凸包算法入门  可查看链接：http://www.cnblogs.com/dream-it-possible/p/8514706.html

/*

author:谦智

圈水池  nyoj 78 凸包算法

*/

//Graham扫描法  求解凸包问题

#include<iostream>

#include<algorithm>

using namespace std;

const int N = ;

struct Node{

  int x,y;

  Node() {}

  Node(int x,int y) {

    this->x = x;

    this->y = y;

  }

};

Node st[N];

struct cmp{//将所有的点坐标按照x从小到大排序  x相等时按照y从小到大排序

  bool operator()(const Node& a,const Node& b) {

    if (a.x != b.x) return a.x < b.x;

    return a.y < b.y;

  }

};

int cross(Node a,Node b,Node c) {

//求向量ab和向量ac的叉积 如果结果为正则ab向量转到ac向量上通过逆时针(转的角度为小角) ==》c点在ab的左侧  ==》c相对于 a 的幅角 α 大于 b相对于 a 的幅角 α

  return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);

}

long long dist(Node a,Node b) {//计算两点之间的距离的平方  用于比较故不用求出实际的距离

  return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);

}

bool cmp1(const Node& a,const Node& b) {// 相对于 st[0] 的幅角 α从小到大排序

  int m = cross(st[],a,b);

  if (m > ) return ;

  if (m ==  && dist(st[],a) <= dist(st[],a)) return ;

  return ;

}

int main() {

  int t;

  cin >> t;

  Node node[];

  while (t--) {

    int n;

    cin >> n;

    for (int i = ; i < n; i++) {

      cin >> node[i].x >> node[i].y;

    }

    sort(node,node+n,cmp());

    int x1,y1,x2,y2;

    st[] = node[];

    sort(node+,node+n,cmp1);

    st[] = node[];

    int top = ;

    for (int i = ; i < n; i++) {

      while (top >  && cross(st[top-],st[top],node[i]) < ) {

        top--;

      }

      st[++top] = node[i];

    }

    sort(st,st+top+,cmp());

    for (int i = ; i <= top; i++) {

      cout << st[i].x << " "<< st[i].y << endl;

    }

  }

}

//用递归算法求出凸包问题 wa

//#include<iostream>

//#include<algorithm>

//using namespace std;

//struct Node{

//  int x,y;

//  Node() {}

//  Node(int x,int y) {

//    this->x = x;

//    this->y = y;

//  }

//};

//struct cmp{

//  bool operator()(const Node& a,const Node& b) {

//    if (a.x != b.x) return a.x < b.x;

//    return a.y < b.y;

//  }

//};

//int cut;

//Node ans[105];

//void getAnsArr(Node node[],int n,int x1,int y1,int x2,int y2) ;

//int main() {

//  int t;

//  cin >> t;

//  Node node[105];

//  while (t--) {

//    int n;

//    cin >> n;

//    for (int i = 0; i < n; i++) {

//      cin >> node[i].x >> node[i].y;

//    }

//    sort(node,node+n,cmp());

//    int x1,y1, x2,y2;

//    x1 = node[0].x;

//    y1 = node[0].y;

//    x2 = node[n-1].x;

//    y2 = node[n-1].y;

//    ans[0] = Node(x1,y1);

//    ans[1] = Node(x2,y2);

//    cut = 2;

//    getAnsArr(node,n,x1,y1,x2,y2);

//    sort(ans,ans+cut,cmp());

//    for (int i = 0; i < cut; i++) {

//      cout << ans[i].x << " " << ans[i].y << endl;

//    }

//  }

//}

//void getAnsArr(Node node[],int n,int x1,int y1,int x2,int y2) {

//  int x3,y3, count = 0;

//  if (n <= 1) return ;

//  x3 = node[0].x;

//  y3 = node[0].y;

//  Node temp[105];

//  int l = x1*y2+x3*y1+x2*y3-x3*y2-x2*y1-x1*y3;

//  int lMax = l;

//  int k = 0;

//  for (int i = 1; i < n; i++) {

//    x3 = node[i].x;

//    y3 = node[i].y;

//    l = x1*y2+x3*y1+x2*y3-x3*y2-x2*y1-x1*y3;

//    if (l >= 0) {

//      temp[count++] = node[i];

//    }

//    if (l > lMax) {

//      lMax = l;

//      k = i;

//    }

//  }

//  if (lMax <= 0) {

//    for (int i = 0; i < count; i++) {

//      x3 = temp[i].x;

//      y3 = temp[i].y;

//      l = x1*y2+x3*y1+x2*y3-x3*y2-x2*y1-x1*y3;

//      if (l == 0 && !((x3==x2&&y3==y2)||(x3==x1&&y3==y1)) ) {

//        ans[cut++] = temp[i];

//      }

//    }

//    return ;

//  } else {

//    ans[cut++] = node[k];

//    if (count == 0) return ;

//  }

//  getAnsArr(temp,count,x1,y1,node[k].x,node[k].y);

//  getAnsArr(temp,count,node[k].x,node[k].y,x2,y2);

//}