2013年8月11日 星期日

2013/8/11 zj d931: C. 幽靈特務報到


// http://zerojudge.tw/ShowProblem?problemid=d931
#include <iostream>
#include <cstdio>
using namespace std;
struct Buildings
{
    double x1, y1, x2, y2;
}b[100000];
double sx, sy, r;
double ds( double a, double b )
{
    double v1 = (sx-a);
    double v2 = (sy-b);
    return v1*v1+v2*v2;  
}
int main()
{
    int t; scanf("%d", &t);
    while( t-- )
    {
        int n; scanf("%d", &n);
       
        for(int i = 0; i < n; i++)
        {
            double tx, ty; double w, l;
            scanf("%lf %lf %lf %lf", &tx, &ty, &w, &l);
            b[i].x1 = tx-(w)/2; b[i].x2 = tx+(w)/2;
            b[i].y1 = ty-(l)/2; b[i].y2 = ty+(l)/2;
           
          //  printf("%lf %lf %lf %lf\n", b[i].x1, b[i].y1, b[i].x2, b[i].y2);
        }
       
       
        scanf("%lf %lf %lf", &sx, &sy, &r);
        r += 0.00001; //避免誤差
        int ans = 0;
        for(int i = 0; i < n; i++)
        {
            double x1 = b[i].x1; double y1 = b[i].y1;
            double x2 = b[i].x2; double y2 = b[i].y2;
           
            if(  x1 <= sx && sx <= x2 && y1 <= sy && sy <= y2){ ans++; }
            else if( sx <= x1 && sy >= y2 )
                {if( ds( x1, y2) <= r*r ) ans++; }
            else if( sx <= x1 && sy <= y1 )
                {if( ds( x1, y1) <= r*r ) ans++; }
            else if( sx >= x2 && sy >= y2 )
                {if( ds( x2, y2) <= r*r ) ans++; }
            else if( sx >= x2 && sy <= y1 )
                {if( ds( x2, y1) <= r*r ) ans++; }
            else if( x1 <= sx && sx <= x2 && sy >= y2)
                {if( sy - y2 <= r ) ans++; }
            else if( x1 <= sx && sx <= x2 && sy <= y1)
                {if( y1 - sy <= r ) ans++; }
            else if( y1 <= sy && sy <= y2 && sx >= x2)
                {if( sx - x2 <= r ) ans++; }
            else if( y1 <= sy && sy <= y2 && sx <= x1)
                {if( x1 - sx <= r ) ans++; }
        }
        printf("%d\n", ans);
    }
}

沒有留言:

張貼留言