Pagini recente » Cod sursa (job #2875866) | Cod sursa (job #2946574) | Cod sursa (job #3130315) | Cod sursa (job #2086181) | Cod sursa (job #629438)
Cod sursa(job #629438)
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,k_st,k_v;
struct pct{double x,y;};
pct v[120001],st[120001],pr,man;
void citire()
{
ifstream fin("infasuratoare.in");
fin>>n;
fin>>v[1].x>>v[1].y;
pr=v[1];
int i2;//poz primului
for (int i=2;i<=n;i++) //pr va fi cel mai din stanga, apoi jos
{
fin>>v[i].x>>v[i].y;
if (v[i].x<pr.x) {pr=v[i]; i2=i;}
if (v[i].x==pr.x && v[i].y<pr.y) {pr=v[i]; i2=i;}
}
man=v[1]; v[1]=pr; v[i2]=man;
fin.close();
}
inline double panta (pct a) {return ((a.y-pr.y)/(a.x-pr.x));}
inline int mai_mic (pct a, pct b) {if (panta(a)<panta(b)) return 1; return 0;}
void mergesort(int i, int mij, int j)
{
pct v2[120001];
int i1=i,i2=mij+1;
int k=0;
while (i1<=mij && i2<=j)
{
if (mai_mic(v[i1],v[i2])==1)
v2[k++]=v[i1++];
else
v2[k++]=v[i2++];
}
while (i1<=mij) v2[k++]=v[i1++];
while (i2<=j) v2[k++]=v[i2++];
int cop=i;
for (int d=0;d<=(j-i);d++)
v[cop++]=v2[d];
}
void sortare(int i, int j)
{
if (i<j)
{
int mij=(i+j)/2;
sortare(i,mij);
sortare(mij+1,j);
mergesort(i,mij,j);
}
}
inline double determinant(pct a, pct b, pct c)
{return (a.x*b.y + a.y*c.x + c.y*b.x - b.y*c.x - c.y*a.x - b.x*a.y);}
void margine(pct a, pct b, pct c)
{
if (determinant(a,b,c)<0)
{
k_st--;
margine(st[k_st-1],st[k_st],v[k_v]);
}
else
{
st[++k_st]=v[k_v++];
if (k_v==n+1) return;
margine(st[k_st-1],st[k_st],v[k_v]);
}
}
int main ()
{
citire();
sortare(2,n);
st[1]=v[1];//primul
st[2]=v[2];//al 2-lea
k_st=2;
k_v=3;
margine(st[k_st-1],st[k_st],v[k_v]);
ofstream fout("infasuratoare.out");
fout.setf(ios::floatfield);
fout.precision(12);
fout<<fixed;
fout<<k_st<<'\n';
for (int i=1;i<=k_st;i++)
fout<<st[i].x<<' '<<st[i].y<<'\n';
fout.close();
return 0;
}