首页 > ACM题库 > HDU-杭电 > HDU 3291-The gold miners[解题报告]HOJ
2014
03-13

HDU 3291-The gold miners[解题报告]HOJ

The gold miners

问题描述 :

There are some funny mini games on the internet. Sailormoon girls usually play these games in them spare time. They always play a mini game named THE GOLD MINNERS. Now they give you a problem about this game. Could you solve it? Now let’s look at the following picture.
  
The magic apple tree

We set the position of the minner as the origin of coordinate.There are many objects in this game,not only gold. They also have diamonds,stones,and other unknown things.All the objects can be treated as polygon. Every two polygons can not intersect. In this problem,we will give you some data about the angle in order. When the hook with certain angle sinking, it will always catch nearest object, and get the corresponding money. There will be nothing in the position of this object later. If there have no objects,the hook will return back to the origin of coordinate. How much money does the minner have at last?Do you know?

输入:

There are multiple test cases.
Each case begins with a positive integer N (0 <= N <= 30) , it means there are N objects.
The following N * 2 lines describe the informatin about objects. Each object starts with a positive integer V (3 <= V <= 15), it means this object can be treated as a polygon with V vertex. Followed by a positive integer W which is the value of this object.
The next line contains V * 2 decimal number. X1,Y1,X2,Y2……Xv,Yv. You can suppose all coordinate data are in the double range.Vertex coordinates clockwise.
Then followed by a positive integer M (M <= 100) which is number of the minner cast hook.
The following M lines contains M positive integer.The Xth integer means the angle with which the minner cast hook the Xth.(0 < angle < 180)

输出:

There are multiple test cases.
Each case begins with a positive integer N (0 <= N <= 30) , it means there are N objects.
The following N * 2 lines describe the informatin about objects. Each object starts with a positive integer V (3 <= V <= 15), it means this object can be treated as a polygon with V vertex. Followed by a positive integer W which is the value of this object.
The next line contains V * 2 decimal number. X1,Y1,X2,Y2……Xv,Yv. You can suppose all coordinate data are in the double range.Vertex coordinates clockwise.
Then followed by a positive integer M (M <= 100) which is number of the minner cast hook.
The following M lines contains M positive integer.The Xth integer means the angle with which the minner cast hook the Xth.(0 < angle < 180)

样例输入:

4
4 158
0.0 -1.0 2.0 -1.0 0.0 -3.0 -1.0 -2.0
4 37
4.0 -1.0 4.0 -2.0 3.0 -2.0 3.0 -1.0
6 360
2.0 -3.0 3.0 -3.0 2.0 -5.0 1.0 -5.0 1.0 -4.0 2.0 -4.0
5 223
-2.0 -4.0 -2.0 -5.0 -3.0 -6.0 -4.0 -5.0 -4.0 -4.0
3
45
16
127

5
4 10
-3.0 0.0 -2.0 -1.0 -3.0 -1.0 -4.0 0.0
4 208
-2.0 0.0 0.0 -1.0 3.0 -1.0 0.0 -3.0
6 660
3.0 -2.0 4.0 -2.0 5.0 -3.0 6.0 -3.0 6.0 -6.0 3.0 -6.0
4 25
-1.0 -4.0 2.0 -4.0 2.0 -6.0 -1.0 -6.0
3 18
0.0 -7.0 1.0 -8.0 -1.0 -8.0
3
34
64
90

样例输出:

418
251

数据就是变态 直接让我那个完全没精度的破模板wa上10几次

膜拜AC大神!

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-9;
const double maxl=1e10;
const double pi=3.1415926535897932384626433832795;
const int maxv=20;
template <class T>
T Max(T a,T b){return a>b?a:b;}
template <class T>
T Min(T a,T b){return a<b?a:b;}
double sqr(double a){return a*a;}
int sgn(double a){if (a>eps) return 1;if (a<-eps) return -1;return 0;}
struct Point
{
double x,y;
Point(){};
Point(double dx,double dy){x=dx;y=dy;}
inline int init(){ return scanf("%lf%lf",&x,&y); }

};
double dis(Point a,Point b);
Point operator -(Point a,Point b){Point c;c.x=a.x-b.x;c.y=a.y-b.y;return c;}
Point operator +(Point a,Point b){Point c;c.x=a.x+b.x;c.y=a.y+b.y;return c;}
Point operator *(Point a,double d){Point c;c.x=a.x*d;c.y=a.y*d;return c;}
Point operator *(double d,Point a){Point c;c.x=a.x*d;c.y=a.y*d;return c;}
Point operator /(Point a,double d){Point c;c.x=a.x/d;c.y=a.y/d;return c;}
double operator *(Point a,Point b){return a.x*b.x+a.y*b.y;}
int operator ==(Point a,Point b){return dis(a,b)<eps;}
int operator !=(Point a,Point b){return dis(a,b)>=eps;}
bool operator < (const Point &l, const Point &r){return sgn(l.y-r.y)<0 ||( sgn(l.y-r.y)==0 && sgn(l.x-r.x)<0 );}
double dis(Point a,Point b){a=a-b;return sqrt(sqr(a.x)+sqr(a.y));}
double crossmuti(Point a,Point b){return a.x*b.y-a.y*b.x;}
struct LineSegment
{
Point pt1,pt2;
LineSegment(){};
LineSegment(Point p1,Point p2){pt1=p1;pt2=p2;}
};
/*
int Intersect(LineSegment L1, LineSegment L2)
{
if( (Max(L1.pt1.x, L1.pt2.x) >= Min(L2.pt1.x, L2.pt2.x)) &&
   (Max(L2.pt1.x, L2.pt2.x) >= Min(L1.pt1.x, L1.pt2.x)) &&
   (Max(L1.pt1.y, L1.pt2.y) >= Min(L2.pt1.y, L2.pt2.y)) &&
   (Max(L2.pt1.y, L2.pt2.y) >= Min(L1.pt1.y, L1.pt2.y)) &&
   (crossmuti(L2.pt1-L1.pt1,L1.pt2-L1.pt1) * crossmuti(L1.pt2-L1.pt1,L2.pt2-L1.pt1) > eps) &&
   (crossmuti(L1.pt1-L2.pt1,L2.pt2-L2.pt1) * crossmuti(L2.pt2-L2.pt1,L1.pt2-L2.pt1) > eps) ) return 1;

if( (Max(L1.pt1.x, L1.pt2.x)+eps >= Min(L2.pt1.x, L2.pt2.x)) &&
   (Max(L2.pt1.x, L2.pt2.x)+eps >= Min(L1.pt1.x, L1.pt2.x)) &&
   (Max(L1.pt1.y, L1.pt2.y)+eps >= Min(L2.pt1.y, L2.pt2.y)) &&
   (Max(L2.pt1.y, L2.pt2.y)+eps >= Min(L1.pt1.y, L1.pt2.y)) &&
   (sgn(crossmuti(L2.pt1-L1.pt1,L1.pt2-L1.pt1)) * sgn(crossmuti(L1.pt2-L1.pt1,L2.pt2-L1.pt1)) >= 0) &&
   (sgn(crossmuti(L1.pt1-L2.pt1,L2.pt2-L2.pt1)) * sgn(crossmuti(L2.pt2-L2.pt1,L1.pt2-L2.pt1)) >= 0) ) return -1;
return 0;
}
*/
struct Polygon
{
Point vertex[maxv];
int numv;
Polygon(){numv=0;}
Polygon(Point *s,int num){numv=num;memcpy(vertex,s,num*sizeof(Point));}
Point &operator [](int k){return vertex[k];}
};

struct Line
{
double a,b,c;   //ax+by+c==0
Line(){};
Line(double p,double q,double r){a=p;b=q;c=r;}
Line(Point p,Point q) //将点q-〉p专成半平面 直线和法向量成右手螺旋
{
   a=q.y-p.y;
   b=p.x-q.x;
   c=p.y*q.x-p.x*q.y;
   double one=sqrt(sqr(a)+sqr(b));
   if (one>0) {a/=one;b/=one;c/=one;}
}  
Line(LineSegment l)
{
   Line ls(l.pt1,l.pt2);
   a=ls.a;b=ls.b;c=ls.c;
}
double func(Point &p){return a*p.x+b*p.y+c;}
};
int ondiffside(Line l,Point a,Point b)
{
return sgn(l.func(a))*sgn(l.func(b))<0;
}
int PntonSeg(LineSegment ls,Point p)
{
Line l(ls.pt1,ls.pt2);
if (ls.pt1==p||ls.pt2==p) return 1;
if (sgn(l.func(p))==0&&((ls.pt1<p&&p<ls.pt2)||(ls.pt2<p&&p<ls.pt1))) return 1;
return 0;
}
int Intersect(LineSegment L1, LineSegment L2)
{
if (ondiffside(L1,L2.pt1,L2.pt2)&&ondiffside(L2,L1.pt1,L1.pt2))
   return 1;
if (PntonSeg(L1,L2.pt1)||PntonSeg(L1,L2.pt2)||PntonSeg(L2,L1.pt1)||PntonSeg(L2,L1.pt2))
   return -1;
return 0;
}
int intersection(Line p,Line q,Point &s)
{
if (sgn(p.a*q.b-p.b*q.a)==0) return 0;
s.y=(p.a*q.c-p.c*q.a)/(q.a*p.b-p.a*q.b);
s.x=(p.b*q.c-p.c*q.b)/(p.a*q.b-p.b*q.a);
return 1;
}

//////////////////////////////////////////////////////////
int poly_lineSg_cross(Polygon &p,LineSegment l,Point &s)
{
int i;
int n=p.numv;
if (n==0) return 0;
p[n]=p[0];
Point t;
int find=0;
for (i=0;i<n;i++)
   if (Intersect(LineSegment(p[i],p[i+1]),l))
   {
    if (intersection(Line(p[i],p[i+1]),Line(l.pt1,l.pt2),t)==0)
     t=p[i];
    if (find==0||dis(Point(0,0),t)<dis(Point(0,0),s))
     s=t;
    find=1;
   }
return find;
}
Polygon p[50];
int w[50];
int n,m;
int cat[50];
Point ins[50];
void work()
{
int i,j,k;
int tot=0;
for (i=0;i<n;i++)
{
   scanf("%d%d",&p[i].numv,w+i);
   for (j=0;j<p[i].numv;j++) p[i][j].init();
}
scanf("%d",&m);
while (m–)
{
   scanf("%d",&k);
   LineSegment l;
   l.pt1=Point(0,0);
   l.pt2=maxl*Point(cos((double)-k/180.0*pi),sin((double)-k/180.0*pi));
   for (i=0;i<n;i++)
    cat[i]=poly_lineSg_cross(p[i],l,ins[i]);
   int t=-1;
   for (i=0;i<n;i++)
    if (cat[i])
     if (t==-1||dis(Point(0,0),ins[i])<dis(Point(0,0),ins[t]))
      t=i;
   if (t>=0)
   {
    p[t].numv=0;
    tot+=w[t];
    w[t]=0;
   }
}
printf("%d\n",tot);
}
int main()
{
freopen("in.in","r",stdin);
while (scanf("%d",&n)!=EOF)
   work();
return 0;
}

参考:http://hi.baidu.com/lccycc_acm/item/2ab73017bd07525c2a3e22bd


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。