2015年3月15日 星期日

2015/03/15 TIOJ 1045 . A.細菌培養

// http://tioj.ck.tp.edu.tw/problems/1045
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

vector<int> v;
vector<int> r;

int N;
int X[300][2];
int Y[300][2];

bool cmp(int a, int b)
{
    int x1, x2;

    if( a > 0 ) x1 = X[a][0];
    else x1 = X[-a][1];

    if( b > 0 ) x2 = X[b][0];
    else x2 = X[-b][1];

    return x1 < x2;
}

int dis(int a, int b)
{
    int x1, x2;

    if( a > 0 ) x1 = X[a][0];
    else x1 = X[-a][1];

    if( b > 0 ) x2 = X[b][0];
    else x2 = X[-b][1];

    return x2-x1;
}

bool cmp2(int a, int b)
{
    return abs(a) < abs(b);
}

ll pwd2(int n)
{
    if( n == 0 ) return 1;

    ll p = pwd2(n/2);

    if( n&1 ) return p*p*2;
    else return p*p;
}

ll update()
{
    sort(r.begin(), r.end(), cmp2);

    ll re = 0;
    int cnt = 0;

    for(int ri = 0; ri < r.size(); ri++)
    {
        if( ri && cmp2(r[ri-1], r[ri]) )
        {
            int d = abs(r[ri])-abs(r[ri-1]);
            re += d*(pwd2(cnt)-1);
        }

        if( r[ri] >= 0 ) cnt++;
        else cnt--;
    }

    return re;
}

int main()
{

    while( scanf("%d", &N) )
    {

        if( !N ) break;

        ll Ans = 100000000;

        v.clear();
        r.clear();

        for(int Ni = 1; Ni <= N; Ni++)
        {
            scanf("%d %d", &X[Ni][0], &Y[Ni][0]);
            scanf("%d %d", &X[Ni][1], &Y[Ni][1]);

            v.push_back(Ni);
            v.push_back(-Ni);
        }

        sort(v.begin(), v.end(), cmp);

        for(int Ni = 0; Ni < N*2; Ni++)
        {
            if( Ni && cmp(v[Ni-1], v[Ni]) )
            {
                ll p = update();
                Ans += p*dis(v[Ni-1], v[Ni]);
            }

            if( v[Ni] > 0 )
            {
                r.push_back(Y[v[Ni] ][0] );
                r.push_back(-Y[v[Ni] ][1] );
            }
            else
            {
                r.erase(find(r.begin(), r.end(), Y[-v[Ni] ][0]) );
                r.erase(find(r.begin(), r.end(), -Y[-v[Ni] ][1]) );
            }
        }

        printf("%lld\n", Ans);

    }
}

沒有留言:

張貼留言