ZOJ 3379. Master Spark

September 2nd, 2010 · Alice Scarlett · ZOJ No comments

Brief description :

假设摸你傻的魔炮是一个角度可选，射程无限，伤害区域是二次项系数为a，顶点在原点的抛物线。二维平面内有一些妖精，问摸你傻的一次魔炮最多能伤害多少妖精。 /#.#/

Analyse :

离散化以后用扫描线，不过要注意的是目标是个环形，因此需要添加一些额外的处理。我的方法是原地再重写一遍。

/*
    Author: xiaodao
    Prog: ZOJ 3379. Master Spark
    Status: Accepted
    Last modify: GMT +8. Aug 29th 21:22
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 32768;
struct record{
    double key;
    int sign;
    friend bool operator <(record a, record b){
        return a.key<b.key; //|| a.key==b.key && a.sign > b.sign;
    }
} scan_line[4*N];
double x[N], y[N], a;
int n, ans;
 
 
void init(){
    a = fabs(a);
    double x, y, t, d, zz, aa = a * a;
    double x0, y0;
    for (int i=0;i<n;i++) scanf("%lf", ::x+i);
    for (int i=0;i<n;i++) scanf("%lf", ::y+i);
 
    for (int i=0;i<n;i++){
        x = ::x[i]; y = ::y[i]; zz = x*x + y*y; t = atan2(y, x);
        y0 = (sqrt(1+4*aa*zz)-1)/(2*a);
        x0 = sqrt(y0/a); d = atan2(x0, y0);
        scan_line[2*i].key = t - d; scan_line[2*i].sign = 1;
        scan_line[2*i+1].key = t + d; scan_line[2*i+1].sign = -1;
    }
 
    /* 破环为链 */
    for (int i=0;i<n;i++){
        scan_line[2*n+2*i] = scan_line[2*i]; scan_line[2*n+2*i].key += 2 * M_PI;
        scan_line[2*n+2*i+1] = scan_line[2*i+1]; scan_line[2*n+2*i+1].key += 2 * M_PI;
    }
}
 
void stat(){
    ans = 0; int sum = 0;
    sort(scan_line, scan_line + 4*n);
    for (int i=0;i<4*n;i++){
        sum += scan_line[i].sign;
        ans = max(ans, sum);
    }
}
 
 
int main(){
    while (scanf("%d%lf", &n, &a)!=EOF){
        init(); stat();
        printf("%d daze\n", ans);
    }
}