2016年12月13日 星期二

ACM Dhaka regional 2015 J. The Hypnotic Spirals

/* 
    題目連結 
    
    有些麻煩要注意一些 case
    1.沒有點 的話 答案是 0
    2.有點 但沒射線 答案是 -1
    
    為了方便 我們把 v[0]+2*pi 再丟進去
    這是為了確保每個點的角度都能被 兩條射線的角度給夾住
    我們將 < v[0] 的 ang += 2*pi 也是為了同樣的目的

    接著是簡易的面積積分
    算完得到 func = a*a*x*x*x/6
    考慮比較普遍的情況 可以得到該點所在的面積
    是四個角度的 func 相加減
    而有些特殊情況 角度不會有四個
    觀察知依原本的解法 那些"不存在的角度" 會解出負的角度
    使這些負的東西的 func 為 0 即可解決
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <queue>
#include <cmath>
#include <set>

using namespace std;

typedef long long ll;

double const pi = acos(-1.0);
double r[10001], ang[10001];

double a;

double func(double x)
{
    if ( x < 0 ) return 0;
    return a*a/6*x*x*x;
}

int main()
{
    int T;
    scanf("%d", &T);

    for (int Ti = 1; Ti <= T; Ti++) {
        scanf("%lf", &a);

        int n;
        scanf("%d", &n);

        vector<double> v;
        for (int ni = 0; ni < n; ni++) {
            double t;
            scanf("%lf", &t);
            v.push_back(t);
        }

        sort(v.begin(), v.end());
        if ( n ) v.push_back(v[0]+pi*2 );

        int m;
        scanf("%d", &m);

        for (int mi = 0; mi < m; mi++) {
            scanf("%lf %lf", &r[mi], &ang[mi]);
            if ( n && ang[mi] < v[0] ) ang[mi] += 2*pi;
        }

        printf("Spiral %d: ", Ti);

        set<double> s;

        if ( m == 0 ) {
            puts("0.0000 liters");
        } else if ( n == 0 ) {
            puts("-1");
        } else {
            double ans = 0;

            for (int mi = 0; mi < m; mi++) {
                int t = -1;
                for (int ni = 0; ni < n; ni++) {
                    if ( v[ni] < ang[mi] && ang[mi] < v[ni+1] ) {
                        t = ni;
                        break;
                    }
                }

                double p = floor((r[mi]/a-ang[mi])/pi/2);

                if ( s.find(p*2*pi+v[t]) == s.end() ) {
                    s.insert(p*2*pi+v[t]);

                    ans -= func(p*2*pi+v[t+1])-func(p*2*pi+v[t]);
                    ans += func((p+1)*2*pi+v[t+1])-func((p+1)*2*pi+v[t]);
                }
            }

            printf("%.4f liters\n", (double)ans/10);
        }
    }
}

沒有留言:

張貼留言