Cod sursa(job #1337902)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 9 februarie 2015 16:59:01
Problema Popandai Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 305

using namespace std;

const long double INF=2000000000;

struct el
{
    int nr;
    long double aria;
} v1[Nmax],v2[Nmax];

struct Point
{
    int x,y;
    bool operator <(const Point A) const
    {
        return x<A.x;
    }
} a[Nmax];
int pc[Nmax][Nmax],n,len1,len2;
long double minim[Nmax];

inline long long Semn(Point A, Point B, Point C)
{
    return (1LL*(B.y-A.y)*C.x + 1LL*(A.x-B.x)*C.y + 1LL*B.x*A.y - 1LL*A.x*B.y);
}

inline long double Arie(Point A, Point B, Point C)
{
    return 0.5*(double)abs(1LL*A.x*B.y + 1LL*B.x*C.y + 1LL*C.x*A.y - 1LL*C.x*B.y - 1LL*A.x*C.y - 1LL*B.x*A.y);
}

int main()
{
    int i,j,k,nr;
    long double sol=INF;
    el w;
    ifstream fin ("popandai.in");
    ofstream fout ("popandai.out");
    fin>>n>>nr;
    for(i=1;i<=n;++i) fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
            for(k=1;k<=n;++k)
                if(a[k].x>a[i].x && a[k].x<a[j].x && a[k].y>0 && Semn(a[i],a[j],a[k])>0)
                {
                    ++pc[i][j];
                    ++pc[j][i];
                }
    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
        {
            for(k=1,len1=len2=0;k<=n;++k)
                if(Semn(a[i],a[j],a[k])>0)
                {
                    //fout<<"jos "<<a[k].x<<" "<<a[k].y<<"\n";
                    w.aria=Arie(a[i],a[j],a[k]);
                    w.nr=pc[i][j]-pc[i][k]-pc[k][j];
                    v1[++len1]=w;
                }
                else
                    if(Semn(a[i],a[j],a[k])<0)
                    {
                        //fout<<"sus "<<a[k].x<<" "<<a[k].y<<"\n";
                        w.aria=Arie(a[i],a[j],a[k]);
                        w.nr=pc[i][k]+pc[k][j]-pc[i][j];
                        v2[++len2]=w;
                    }
            for(k=0;k<=n;++k) minim[k]=INF;
            for(k=1;k<=len2;++k) minim[v2[k].nr]=min(minim[v2[k].nr],v2[k].aria);
            for(k=n-1;k>=0;--k) minim[k]=min(minim[k+1],minim[k]);
            for(k=1;k<=len1;++k)
                sol=min(sol,minim[max(nr-v1[k].nr,0)]+v1[k].aria);
        }
    fout<<setprecision(2)<<fixed<<sol<<"\n";
    return 0;
}