POJ 3996 Air Strike

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 389 Accepted: 130

Description

General Gee is the commander of a military base. He has just received alarming news from one of his spies: the enemy’s preparing an air missile strike. The base contains two magnetic towers. When activated and given sufficient power, each of the magnetic towers creates a powerful horizontal magnetic disk. If any missile passes through this disk it deflects away from the base. Although those towers seem to be an excellent air defense method, there is a problem: The area of the disk generated by a tower is proportional to the amount of energy it receives. The base has enough power plants to generate a certain amount of energy, which has to be divided among those two towers. That means that the total area of the two disks generated from the towers should not exceed the total energy generated by the power plants. Fortunately, the spy was able to know the exact target co-ordinates of the incoming missiles and he reported them to General Gee. The General needs your help in distributing the energy on the two magnetic towers to minimize the number of missiles that will not get deflected by the magnetic towers and therefore will hit the base. You may assume the following: 

 

The towers have different heights and therefore there are no problems associated with the magnetic disks interfering with each other.

A missile will deflect if it passes through the magnetic disk of a tower or even if it just touches its boundary.

A missile hitting a tower (landing exactly on its location) will deflect, even if the tower is not given any energy.

All incoming missiles will go down simultaneously at the exact instant; therefore, there will not be any time available to redistribute the energy amongst the two towers during the strike.

Input

Input consists of several test cases. Each test case is specified on N+2 lines. The first line contains an integer (1 ≤ N ≤ 1, 000) representing the number of missiles. The second line contains 5 real numbers X1, Y1, X2, Y2 and T: (X1, Y1) is the coordinates of the first tower, (X2, Y2) is the coordinates of the second tower and (0 ≤ T) is the total amount of energy generated from the power plants (the total area of the two magnetic disks). Each line of the remaining N lines contains two real numbers representing the landing coordinates of a missile. 

The absolute value of all the given real numbers is less than or equal to 100 and may include a decimal point followed by up to 3 digits. Any two consecutive numbers on the same line are separated by one or more white-space characters. Zero or more blank lines may appear between test cases. 

The last line of the input file is made of a single zero.

Output

For each test case, print the following line: 

k. M 

Where k is the test case number (starting at one,) and M is the minimum number of missiles that will NOT be deflected in the best distribution of energy among the two towers. Use π = 3.141.

Sample Input

6

-3 0 3 0 40.833

-1 4

-2 2.5

1 2

5 2

-4 0

-3 -1

 

2

0 0 1 1 0

0 0

1 1

 

0

Sample Output

1. 2

2. 0

Hint

 

Source

anarc 2009

 

题目大意：就是给定两个圆的圆心，以及两个圆的面积相加之和，再给定一系列点，要你分配这两个圆面积，使得圆覆盖的点做多，求至少多少点未被覆盖。

 

 

解题思路：很水，只需枚举圆的半径即可。

 

 

 

#include <iostream>  
#include <cstdio>  
#include <cmath>  
#include <algorithm>  
using namespace std;  
  
const double pi=3.141;  
const int maxn=1000;  
  
struct point{  
    double x,y;  
    double getdis(point p){  
        return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));  
    }  
};  
  
point a,b;  
int n,casen=0;  
double disa[maxn+10],disb[maxn+10],sum;  
  
void input(){  
    point p;  
    scanf("%lf%lf",&a.x,&a.y);  
    scanf("%lf%lf",&b.x,&b.y);  
    scanf("%lf",&sum);  
    for(int i=0;i<n;i++){  
        scanf("%lf%lf",&p.x,&p.y);  
        disa[i]=p.getdis(a);  
        disb[i]=p.getdis(b);  
    }  
}  
  
void computing(){  
    int ans=0;  
    double ra,rb;  
    for(int i=0;i<n;i++){  
        int tmp=0;  
        ra=disa[i];  
        if(pi*ra*ra>sum) continue;  
        rb=sqrt(max(sum/pi-ra*ra,0.000));  
        for(int j=0;j<n;j++){  
            if(disa[j]<=ra || disb[j]<=rb){  
                tmp++;  
            }  
        }  
        if(tmp>ans) ans=tmp;  
    }  
    for(int i=0;i<n;i++){  
        int tmp=0;  
        rb=disb[i];  
        if(pi*rb*rb>sum) continue;  
        ra=sqrt(max(sum/pi-rb*rb,0.000));  
        for(int j=0;j<n;j++){  
            if(disa[j]<=ra || disb[j]<=rb){  
                tmp++;  
            }  
        }  
        if(tmp>ans) ans=tmp;  
    }  
    casen++;  
    printf("%d. %d\n",casen,n-ans);  
}  
  
int main(){  
    while(scanf("%d",&n)!=EOF && n){  
        input();  
        computing();  
    }  
    return 0;  
}  

 

补充：软件开发 , C++ ,