圈水池
时间限制：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原题链接：?pid=78典型的凸包问题，直接上代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 typedef struct 4 { 5int x,y; 6 } point; 7 point pnt[100],res[100]; 8 bool mult(point sp,point ep,point op) 9 {10return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);11 }*a,const void*b)13 {14point *p1=(point*)a,*p2=(point*)b;15if(p1->x==p2->x) return p1->y>p2->y;p1->x>p2->x;17 }18 int graham(int n)19 {20int i,len,top=1;;22res[0]=pnt[0];;24res[1]=pnt[1];;26for(i=2;i<n;i++)27 {28while(top&&mult(pnt[i],res[top],res[top-1])) top–;29res[++top]=pnt[i];30 }31len=top;32res[++top]=pnt[n-2];33for(i=n-3;i>=0;i–)34 {35while(top!=len&&mult(pnt[i],res[top],res[top-1])) top–;36res[++top]=pnt[i];37 }38return top;39 }40 int main()41 {42int m,n,i;,&m);44while(m–)45 {,&n);47for(i=0;i<n;i++)48 {,&pnt[i].x,&pnt[i].y);50 }51qsort(pnt,n,sizeof(point),camp);52n=graham(n);53qsort(res,n,sizeof(point),camp);54for(i=0;i<n;i++)55 {,res[i].x,res[i].y);57 }58 };60 }
posted on
生命不在长而在于好，只要每一次尽力的演示，都值得鼓励与喝采。
