圈水池
时间限制：3000 ms | 内存限制：65535 KB
难度：4
- 描述
- 有一个牧场，牧场上有很多个供水装置，现在牧场的主人想要用篱笆把这些供水装置圈起来，以防止不是自己的牲畜来喝水，各个水池都标有各自的坐标，现在要你写一个程序利用最短的篱笆将这些供水装置圈起来！（篱笆足够多，并且长度可变）
- 输入
- 第一行输入的是N,代表用N组测试数据（1<=N<=10）
第二行输入的是m,代表本组测试数据共有m个供水装置（3<=m<=100）
接下来m行代表的是各个供水装置的横纵坐标 - 输出
- 输出各个篱笆经过各个供水装置的坐标点，并且按照x轴坐标值从小到大输出，如果x轴坐标值相同，再安照y轴坐标值从小到大输出
- 样例输入
-
1
4
0 0
1 1
2 3
3 0 - 样例输出
-
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);
//}