Cod sursa(job #983419)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 11 august 2013 19:15:36
Problema Patrate2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

ifstream fin("gold.in");
ofstream fout("gold.out");

const int N = 1040;

typedef pair <int, int> punct;
typedef pair <punct, int> pct;
int sol, n, eps, stot, gold[N];
punct p0, pd, v[N]; pct vo[N];

inline bool cmp(const pct& a, const pct& b)
{
    punct p1 = a.first, p2 = b.first;
    return ((p1.x-p0.x) * (p2.y-p0.y) - (p2.x-p0.x) * (p1.y-p0.y) > 0);
}

inline bool side(punct p1, punct p2, punct p3)
{
    return ((p3.y-p1.y) * (p2.x-p1.x) - (p3.x-p1.x) * (p2.y-p1.y) > 0);
}

inline bool cmp2(const pct& a, const pct& b)
{
    punct aa = a.first, bb = b.first;
    double r1 = atan2((double)(aa.y - p0.y), (double)(aa.x - p0.x));
    double r2 = atan2((double)(bb.y - p0.y), (double)(bb.x - p0.x));
    return r1 < r2;
}

void Center(punct p, int poz)
{
    p0 = p;
    for(int i=1; i<=n; i++) vo[i].first = v[i], vo[i].second = i;
    swap(vo[1], vo[poz]);
    if(n > 200) sort(vo+2, vo+n+1, cmp);
    else sort(vo+2, vo+n+1, cmp2);

    int sum = 0, last = 0;
    for(int i=3; ; i++)
    {
        if(i == n+1) i = 2;
        if(!side(p, vo[2].first, vo[i].first))
        { last = i; break;}
        sum += gold[vo[i].second];
    }
    //cout<<vo[last].second;
    if(abs(stot - sum - gold[poz] - gold[vo[2].second] - sum) <= eps) sol++;

    for(int i=3; i<=n; i++)
    {
        if(sum) sum -= gold[vo[i].second];
        //if(sum < 0) sum = 0, last = i+1; if(last == n + 1) last = 2;
        if(last == i) last++;
        for(int j=last;  ; j++)
        {
            if(j == n + 1) j = 2;
            if(!side(p, vo[i].first, vo[j].first))
            { last = j; break;}
            sum += gold[vo[j].second];
        }
        //cout<<sum<<' '<<vo[i].second<<endl;
        if(abs(stot - gold[poz] - gold[vo[i].second] - sum - sum) <= eps) sol++;
    }
}

int main()
{
    fin>>n>>eps;
    for(int i=1; i<=n; i++)
        fin>>gold[i];
    for(int i=1; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
        stot += gold[i];
    }
    for(int i=1; i<=n; i++)
    {
        Center(v[i], i);
        //break;
    }
    fout<<sol/2;
    return 0;
}