首页 > ACM题库 > HDU-杭电 > HDU 2948-Geometry Darts-计算几何-[解题报告]HOJ
2014
02-24

HDU 2948-Geometry Darts-计算几何-[解题报告]HOJ

Geometry Darts

问题描述 :

Bob and Hannah like to play darts. They are not very good at it, however, so finishing a round of 501 Darts will take an eternity. They therefore decide to throw away the dartboard completely and put geometric shapes on the wall instead, awarding points according to the number of shapes the dart penetrates. To reduce the complexity of scoring, they only use circles, triangles and rectangles.


A game consists of each person throwing 3 darts each, and your job is to find the winner of the game, given the shapes and the throws.

输入:

The input will start with a line giving the total number of shapes, S. Then follow S lines describing the shapes, in either of the following formats:

1. C x y r, where (x, y) is the center of the circle, and r is the radius.

2. R x1 y1 x2 y2, where (x1, y1) and (x2, y2) are two corners of the rectangle with x1 < x2 and y1 < y2.

3. T x1 y1 x2 y2 x3 y3, where (xi, yi) are the three corners of the triangle.

Then follows a line with N, the number of games Bob and Hannah play. Each game is described with six lines giving the x and y coordinates of the 6 throws, the first three by Bob and the last three by Hannah.

输出:

The input will start with a line giving the total number of shapes, S. Then follow S lines describing the shapes, in either of the following formats:

1. C x y r, where (x, y) is the center of the circle, and r is the radius.

2. R x1 y1 x2 y2, where (x1, y1) and (x2, y2) are two corners of the rectangle with x1 < x2 and y1 < y2.

3. T x1 y1 x2 y2 x3 y3, where (xi, yi) are the three corners of the triangle.

Then follows a line with N, the number of games Bob and Hannah play. Each game is described with six lines giving the x and y coordinates of the 6 throws, the first three by Bob and the last three by Hannah.

样例输入:

3
C 0.0 0.0 5.0
R -1.0 -1.0 7.0 7.0
T 0.0 0.0 -3.0 0.0 0.0 -8.0
1
0.0 4.1
0.0 6.2
0.0 8.1
-0.5 -0.5
-0.5 -2.0
-0.5 -5.1

样例输出:

Hannah


//Point 在 Circle, Rectangle and Triangle 里的判定,都很简单 //其中, 点(p)在三角形(p1, p2, p3)内部, 有 p2 , p3 在 p-p1的两边 , 同理有p1, p3 在 p-p2的两边,利用叉积即可判定 #include <iostream>#include <cmath>#include <algorithm> using namespace std; const double EPS = 1e-8;const double PI  = acos(-1.0);const int    MAX_N= 1010; struct Point { double x, y;}; struct Circle { double x, y, r;}; struct Rectangle { double x1, y1, x2, y2;}; struct Triangle { Point p1, p2, p3;}; Circle c[MAX_N];Rectangle r[MAX_N];Triangle t[MAX_N];int nc, nr, nt; int Rlcmp(const double &a, const double &b){ if (fabs(a-b) < EPS)  return 0; return a > b ? 1 : -1;} Point operator-(const Point &p1, const Point &p2){ Point ret; ret.x = p1.x – p2.x; ret.y = p1.y – p2.y; return ret;} double CrossProduct(const Point &p1, const Point &p2){ return p1.x*p2.y – p2.x*p1.y;} double Distance(const double &x1, const double &y1, const double &x2, const double &y2) { return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));} double Max(const double &a, const double &b){ return a > b ? a : b;}double Min(const double &a, const double &b){ return a > b ? b : a;} bool InCircle(const Circle &c, const Point &p){ double d = Distance(c.x, c.y, p.x, p.y);  if (Rlcmp(c.r, d) == 1)  return true;  return false;}bool InRectangle(const Rectangle &r, const Point &p){  if (Max(r.x1, r.x2) – p.x > EPS   && p.x – Min(r.x1, r.x2) > EPS  && Max(r.y1, r.y2) – p.y > EPS  && p.y – Min(r.y1, r.y2) > EPS)  return true;  return false;}bool InTriangle(const Triangle &t, const Point &p){  if (CrossProduct(p-t.p1, t.p2-t.p1) * CrossProduct(p-t.p1, t.p3-t.p1) < 0  && CrossProduct(p-t.p2, t.p1-t.p2) * CrossProduct(p-t.p2, t.p3-t.p2) < 0)  return true;  return false;}int Count(const Point &p){ int cnt = 0; int i;  for (i=0; i<nc; ++i) {  if (InCircle(c[i], p))   cnt++; }  for (i=0; i<nr; ++i) {  if (InRectangle(r[i], p))   cnt++; }  for (i=0; i<nt; ++i) {  if (InTriangle(t[i], p))   cnt++; }  return cnt;} bool do_case(){ int s, n; nc = nt = nr = 0;  for (scanf(“%d\n”, &s); s–; ) {  char ch = getchar();  if (ch == ‘C’) {   scanf(“%lf %lf %lf\n”, &c[nc].x, &c[nc].y, &c[nc].r);   nc++;  }  else if (ch == ‘R’) {   scanf(“%lf %lf %lf %lf\n”, &r[nr].x1, &r[nr].y1, &r[nr].x2, &r[nr].y2);   nr++;  }  else {   scanf(“%lf %lf %lf %lf %lf %lf\n”, &t[nt].p1.x, &t[nt].p1.y, &t[nt].p2.x, &t[nt].p2.y, &t[nt].p3.x, &t[nt].p3.y);   nt++;  } }  for (scanf(“%d”, &n); n–; ) {  int b=0, h=0;  Point p;  int i, tmp = 3;    for (i=0; i<tmp; ++i) {   scanf(“%lf %lf”, &p.x, &p.y);   b += Count(p);  }   for (i=0; i<tmp; ++i) {   scanf(“%lf %lf”, &p.x, &p.y);   h += Count(p);  }   if (b > h)   printf(“Bob\n”);  else if (b < h)   printf(“Hannah\n”);  else    printf(“Tied\n”); } return true;} int main(void) {  do_case()  ; return true;}
解题参考:http://jidayangfei.blog.163.com/blog/static/1349366082011323105534293/


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }