ZOJ 3575 Under Attack III

ZOJ 3575 Under Attack III

Due to the successful resist in Under Attack II, the enemy lost most of their bombers and our ground forces are advancing for victory. However, our spy has transmitted a shocking intel saying that the insane and desparate enemy set up a crazy plan aiming at our civilians. They will launch nuclear missles to attack prosperous cities in our country ! Doctor has received order from central command to calculate how many cities will be destroyed if the enemy bomber succeed (though the possibility is very little).

According to intel, every nuclear missle has a effect range. The missle's effect range is a ellipse with axis length a parrelling to x axis, axis length b parrelling to y axis.Notice enemy can attack every point. Our spies have got data of the ellipse of missle and now given the cooridinate of cities, please show how many cities will be attacked at most.

Input

The input consists of multiple cases.
The first line are the length a and b of effect ellipse's axises. a b are both in the range of [0,400].a b are both positive floating numbers.
Next line is city number n.n can be up to 200.
Following n lines are x and y non-negative floating numbers cooridinate of each city.
Cities on the edge of ellipse are also regarded as attacked. It's guaranteed that no two cities are at one point.

Output

Output the cities affected at most.

Sample Input

2 3
2
1 1
2 2

Sample Output

2

題意：告訴一個橢圓的長短軸a,b值，以及n個點，求這個橢圓最多能圈住多少個點。

思路：橢圓的話不好處理，所以轉化成圓上問題了，把橢圓方程稍微變換一下。然後枚舉圓心，至於怎麼枚舉，其實只要有兩個點，就能確定一個圓啊（其實是兩個圓）。然後每次枚舉看看哪個情況下圈的最多。注意一點就是，可能點與點之間都隔得很開，不存在同時圈住大於等於2個點的情況，這個時候就要輸出1.

#include 
#include 
#include 
#include 
#include 
#include 
#define eps 1e-6
#define Pi acos(-1.0)
using namespace std;

struct Node
{
    double x,y;
}f[500];

double a,b;
int n;

double dis(double a,double b,double c,double d)
{
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}

int solve(double a,double b,double r)
{
    int num=0;

    for(int i=0;i2*r) continue;
                len/=2;

                double d=sqrt(r*r-len*len);

                double xx,yy;//求中點
                xx=(f[i].x+f[j].x)/2;
                yy=(f[i].y+f[j].y)/2;

                double aa;

                if(f[i].x-f[j].x==0) aa=Pi/2;
                else aa=atan( (f[j].y-f[i].y)/(f[j].x-f[i].x) );

                aa-=Pi/2;

                double x0,y0;//求 圓心
                x0=xx+d*cos(aa);
                y0=yy+d*sin(aa);

                tmp=solve(x0,y0,r);
                ans=max(ans,tmp);

                x0=xx-d*cos(aa);
                y0=yy-d*sin(aa);

                tmp=solve(x0,y0,r);
                ans=max(ans,tmp);

            }
        }
        
        if(ans==0) ans=1;//如果初始化是1，就不用判斷。

        printf(%d
,ans);

    }
    return 0;
}