鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4946

題意：有n個人。在位置（xi,yi），速度是vi，假設對于某個點一個人比全部其它的都能先到那個點，那這個點就被這個人承包了。輸出有多少人承包的（魚塘）面積是無窮大。

思路：找出速度最大值，僅僅有速度是這個最大值的人才有可能承包無窮大的面積（由于快速者早晚會追上低速者）。

每兩個人相比，他們能承包的位置的界線是他們坐標的中垂線，能夠證明的是，在組成凸包時，在凸包里的人。承包的面積一定是有限的。

所以在凸包上的人（包含邊上）才可能承包無窮大的面積。

注意點在于由于題里要求嚴格小于其它人到達的時間才干承包，所以假設出現重點重速的兩個人，那么兩個人都是不能承包的，可是在計算凸包時它們須要計進來由于有可能由于他們的存在導致其它人承包不了。

代碼：

#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <ctype.h> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #define eps 1e-10 #define INF 0x7fffffff #define maxn 10005 #define PI acos(-1.0) #define seed 31//131,1313 typedef long long LL; typedef unsigned long long ULL; using namespace std; int x[505],y[505],v[505],vis[505]; int cmp(double x) {if(fabs(x)<eps)return 0;if(x>0)return 1;return -1; } inline double sqr(double x) {return x*x; } struct point//點 {double x,y;int pos;int o;point() {}point(double a,double b):x(a),y(b) {}void input(){scanf("%lf%lf",&x,&y);}friend point operator + (const point &a,const point &b){return point(a.x+b.x,a.y+b.y);}friend point operator - (const point &a,const point &b){return point(a.x-b.x,a.y-b.y);}friend bool operator == (const point &a,const point &b){return cmp(a.x-b.x)==0 &&cmp(a.y-b.y)==0;}friend point operator * (const point &a,const double &b){return point(a.x*b,a.y*b);}friend point operator * (const double &a,const point &b){return point(a*b.x,a*b.y);}friend point operator / (const point &a,const double &b){return point(a.x/b,a.y/b);}double norm(){return sqrt(sqr(x)+sqr(y));}//到原點距離void out () const{printf("%.2f %.2f",x,y);} } p[505]; double det (const point &a,const point &b) {return a.x*b.y-a.y*b.x; }//叉積 double dot (const point &a,const point &b) {return a.x*b.x+a.y*b.y; }//點乘 double dist (const point &a,const point &b) {return (a-b).norm(); }//距離 point rotate_point(const point &p,double A) {double tx=p.x,ty=p.y;return point (tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A)); }//旋轉，A是弧度 struct polygon_convex {vector <point> P;polygon_convex(int size=0){P.resize(size);} } p_c; bool comp_less(const point &a,const point &b) {return cmp(a.x-b.x)<0||cmp(a.x-b.x)==0&&cmp(a.y-b.y)<0; } polygon_convex convex_hull(vector <point> a) {polygon_convex res(2*a.size()+5);sort(a.begin(),a.end(),comp_less);a.erase(unique(a.begin(),a.end()),a.end());int m=0;for(int i=0; i<a.size(); i++){while(m>1 && cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<0)m--;res.P[m++]=a[i];}int k=m;for(int i=int(a.size())-2; i>=0; i--){while(m>k && cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<0)m--;res.P[m++]=a[i];}res.P.resize(m);if(a.size()>1)res.P.resize(m-1);return res; } bool cmp3(point a,point b) {return a.x<b.x||((a.x==b.x)&&(a.y<b.y)); } int main() {int T,tt=0;while(scanf("%d",&T)){tt++;vector<point>pp;pp.clear();memset(vis,0,sizeof(vis));if(T==0)break;int pos=-1;int max_v=0;for(int i=1; i<=T; i++){scanf("%d%d%d",&x[i],&y[i],&v[i]);if(v[i]>max_v)max_v=v[i];}int top=0;for(int i=1; i<=T; i++){if(v[i]==max_v){p[top].x=(double)x[i];p[top].y=(double)y[i];p[top].pos=i;p[top].o=0;top++;}}printf("Case #%d: ",tt);if(max_v==0){for(int i=1; i<=T; i++)printf("0");printf("\n");continue;}sort(p,p+top,cmp3);for(int i=0; i<top; i++){if((i<top-1&&(p[i].x)==(p[i+1].x)&&(p[i].y)==(p[i+1].y))||(i>0&&(p[i].x)==(p[i-1].x)&&(p[i].y)==(p[i-1].y)))p[i].o=1;}pp.push_back(p[0]);for(int i=1; i<top; i++){if(p[i].x!=p[i-1].x||p[i].y!=p[i-1].y)pp.push_back(p[i]);}if(pp.size()<=3){for(int i=0; i<pp.size(); i++)if(pp[i].o==0)vis[pp[i].pos]=1;}else{polygon_convex ans=convex_hull(pp);for(int i=0; i<ans.P.size(); i++){if(ans.P[i].o==0)vis[ans.P[i].pos]=1;}}for(int i=1; i<=T; i++)printf("%d",vis[i]);printf("\n");}return 0; }

版權聲明：本文博客原創文章，博客，未經同意，不得轉載。

轉載于:https://www.cnblogs.com/mfrbuaa/p/4726900.html

總結

以上是生活随笔為你收集整理的HDU 4946 Area of Mushroom 凸包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。