# Cod sursa(job #2001915)

Utilizator Data 18 iulie 2017 00:56:03 Infasuratoare convexa 10 cpp done Arhiva educationala 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);
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;
}
{
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);
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);
}