Cod sursa(job #2001912)

Utilizator proflaurianPanaete Adrian proflaurian Data 18 iulie 2017 00:30:47
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 4.62 kb
#include <bits/stdc++.h>
//******************************************************************************************************
//*  ALGORITM DIVIDE ET IMPERA PENTRU DETERMINATEA INFASURATORII CONVEXE                               *
//*      - se sorteaza varfurile dupa x                                                                *
//*      - se proceseaza recursiv intervale de indici lo hi ( initial lo=1,hi=n )                      *
//*      - se considera mi=(lo+hi)/2                                                                   *
//*      = se determina infasuratoarea pe intervalele [lo,mi] si [mi+1,hi]                             *
//*      - se 'combina' rezultatele utilizand tangenta superioara si inferioara la cele doua poligoane *
//*      - pentru intervalele mai mici de 6 puncte se determina infasuratoarea brut                    *
//******************************************************************************************************
#define tip double
#define punct pair<tip,tip>
#define X first
#define Y second
#define setp vector< punct >

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int comp(tip,tip);
int cadran(punct);
inline int nxt(int,int);
inline int prv(int,int);
setp P,R,impera(setp,setp,int,int,int,int);
bool trig(punct,punct);
setp brut(int,int);
setp divide(int,int);
tip XG,YG,eps=0.000000000001;
tip det(punct,punct,punct);
int main()
{
    int n;
    f>>n;
    for(int i=1;i<=n;i++)
    {
        double x,y;
        f>>x>>y;
        P.push_back(make_pair(x,y));
    }
    sort(begin(P),end(P));
    R=divide(0,n-1);
    g<<R.size()<<'\n';
    for(auto it:R)
        g<<fixed<<setprecision(10)<<it.X<<' '<<it.Y<<'\n';

    return 0;
}
int cadran(punct A)
{
    return A.X<=0?A.Y>=0?2:3:A.Y>=0?1:4;
}
inline int nxt(int i,int n)
{
    return i==n-1?0:i+1;
}
inline int prv(int i,int n)
{
    return i==0?n-1:i-1;
}
setp impera(setp a,setp b, int i,int j,int k,int l)
{
    setp c;
    c.resize(0);
    //cerr<<a.size()<<' '<<b.size()<<'\n';
    for(int n=a.size();; i=nxt(i,n))
    {
        c.push_back(a[i]);
        if(i==j)break;
    }
    for(int n=b.size();; k=nxt(k,n))
    {
        c.push_back(b[k]);
        if(k==l)break;
    }
    return c;
}
bool trig(punct A,punct B)
{
    A=make_pair(A.X-XG,A.Y-YG);
    B=make_pair(B.X-XG,B.Y-YG);
    if(cadran(A)<cadran(B))return true;
    if(cadran(A)>cadran(B))return false;
    return A.X*B.Y>=A.Y*B.X;
}
setp brut(int L,int R)
{

    set<punct> S;
    int nr=R-L+1;
    for(int i=L; i<R; i++)
        for(int j=L+1; j<=R; j++)
        {
            int poz=0,neg=0;
            for(int k=L; k<=R; k++)
            {
                if(comp(det(P[i],P[j],P[k]),0.0)>=0)poz++;
                if(comp(det(P[i],P[j],P[k]),0.0)<=0)neg++;
            }
            if(poz==nr||neg==nr)
            {
                S.insert(P[i]);
                S.insert(P[j]);
            }
        }
    setp ret;
    ret.resize(0);
    XG=YG=0;
    for(auto it:S)
    {
        ret.push_back(it);
        XG+=it.X;
        YG+=it.Y;
    }
    XG/=(double)ret.size();
    YG/=(double)ret.size();
    sort(ret.begin(),ret.end(),trig);
    return ret;
}
int comp(tip x,tip y)
{
    return (x>y+eps)?1:(y>x+eps)?-1:0;
}
double det(punct A,punct B,punct C)
{
    return A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X;
}
void up_tg(setp a,setp b,int &ia,int &ib)
{

    int na=a.size(),nb=b.size();
    ia=0;for(int i=0;i<na;i++)if(a[i].X>a[ia].X)ia=i;
    ib=0;for(int i=0;i<nb;i++)if(b[i].X<b[ib].X)ib=i;
    int gata=0;
    while(!gata)
    {
        gata=1;
        while(comp(det(b[ib],a[ia],a[nxt(ia,na)]),0.0)<=0)
            ia=nxt(ia,na);
        while(comp(det(a[ia],b[ib],b[prv(ib,nb)]),0.0)>=0)
            ib=prv(ib,nb),gata=0;
    }
}
void lo_tg(setp a,setp b,int &ia,int &ib)
{
    int na=a.size(),nb=b.size();
    ia=0;for(int i=0;i<na;i++)if(a[i].X>a[ia].X)ia=i;
    ib=0;for(int i=0;i<nb;i++)if(b[i].X<b[ib].X)ib=i;
    int gata=0;
    while(!gata)
    {
        gata=1;
        while(comp(det(a[ia],b[ib],b[nxt(ib,nb)]),0.0)<=0)ib=nxt(ib,nb);
        while(comp(det(b[ib],a[ia],a[prv(ia,na)]),0.0)>=0)ia=prv(ia,na),gata=0;
    }
}
setp divide(int lo,int hi)
{

    if(hi-lo+1<=6)return brut(lo,hi);
    int mi=(lo+hi)/2;
    setp a=divide(lo,mi),b=divide(mi+1,hi);
    //for(auto it:a)g<<it.X<<' '<<it.Y<<'\n';g<<'\n';
    //for(auto it:b)g<<it.X<<' '<<it.Y<<'\n';g<<'\n';

    int i,j,k,l;
    up_tg(a,b,i,l);//g<<i<<' '<<l<<'\n';
    lo_tg(a,b,j,k);//g<<j<<' '<<k<<'\n';


    return impera(a,b,i,j,k,l);
}