Pagini recente » Cod sursa (job #273570) | Cod sursa (job #2112918) | Cod sursa (job #756750) | Cod sursa (job #1752458) | Cod sursa (job #1409396)
#include <fstream>
using namespace std;
#define NMax 120005
#define X first
#define Y second
#define szup stup[0]
#define szdown stdown[0]
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
pair<double,double> P[NMax];
int stup[NMax],stdown[NMax];
bool isUpper(int i,int j,int k,bool ok)
{
double a,b;
a = (P[j].Y-P[i].Y)/(P[j].X-P[i].X);
b = P[i].Y - a * P[i].X;
bool rez = true;
if(a<0) rez = ok;
if(P[j].X != P[i].X)
{
if(a*P[k].X + b < P[k].Y) return rez;
return !rez;
}
else return true;
}
void solve_up(int i)
{
while(szup > 1 && !isUpper(stup[szup-1],stup[szup],i,false)) szup--;
stup[++szup] = i;
}
void solve_down(int i)
{
while(szdown > 1 && !isUpper(stdown[szdown-1],stdown[szdown],i,true)) szdown--;
stdown[++szdown] = i;
}
int main()
{
int i;
f>>n;
for(i=1;i<=n;++i) f>>P[i].X>>P[i].Y;
sort(P+1,P+n+1);
stup[++szup] = 1;
stdown[++szdown] = 1;
for(i=2;i<n;++i)
{
if(isUpper(1,n,i,false)) solve_up(i);
else solve_down(i);
}
stdown[++szdown] = n;
for(i=1;i<=szdown;++i) g<<P[stdown[i]].X<<" "<<P[stdown[i]].Y<<"\n";
for(i=szup;i>=2;--i) g<<P[stup[i]].X<<" "<<P[stup[i]].Y<<"\n";
f.close();
g.close();
return 0;
}