Pagini recente » Cod sursa (job #2824503) | Cod sursa (job #706495) | Cod sursa (job #2919239) | Cod sursa (job #924715) | Cod sursa (job #828201)
Cod sursa(job #828201)
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
#define dim 120005
#define fs first
#define sc second
#define inf 0x3f3f3f3f
pair <double,double> v[dim];
int orig=1,ind[dim],n,stiva[dim],vf;
void read()
{
int i;
fin>>n;
for(i=1;i<=n;++i)
{
fin>>v[i].fs >>v[i].sc;
if(v[i].fs<v[orig].fs || (v[i].fs==v[orig].fs && v[i].sc<v[orig].sc))
orig=i;
ind[i]=i;
}
}
inline double panta(int a, int b)
{
if(v[a].fs==v[b].fs)
return inf;
return (v[b].sc-v[a].sc)/(v[b].fs-v[a].fs);
};
struct cmp
{
bool operator () (const int &a, const int &b)
{
return panta(a,orig)<panta(b,orig);
}
};
inline double det(int a, int b, int c)
{
return (v[b].fs-v[a].fs)*(v[c].sc-v[a].sc)-(v[c].fs-v[a].fs)*(v[b].sc-v[a].sc);
};
void solve()
{
sort(ind+1,ind+n+1,cmp());
stiva[++vf]=orig;
for(int i=1;i<=n;++i)
if(ind[i]!=orig)
{
for(;vf>=2 && det(stiva[vf-1],stiva[vf],ind[i])<0;--vf);
stiva[++vf]=ind[i];
}
}
void print()
{
printf("%ld\n",vf);
for(int i=1;i<=vf;++i)
printf("%lf %lf\n",v[stiva[i]].fs,v[stiva[i]].sc);
}
int main()
{
freopen("infasuratoare.out","w",stdout);
read();
solve();
print();
return 0;
}