程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3575 Under Attack III

ZOJ 3575 Under Attack III

編輯:C++入門知識

ZOJ 3575 Under Attack III


 

Under Attack III

Time Limit: 7 Seconds Memory Limit: 65536 KB

 

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;
}

 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved