Pagini recente » Cod sursa (job #1930770) | Cod sursa (job #2010647) | Cod sursa (job #1004247) | Cod sursa (job #698874) | Cod sursa (job #1092258)
#include <fstream>
#include <cstdio>
#include <algorithm>
#include<vector>
#include<stack>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;
int i,n,k,j,p,s,unu,m,doi,q,dr,maxim,maxi2,val,cont,sol,z,ind[120009],orig,stiva[120009],vf;
struct punct
{
double x,y;
}v[120010];
inline double panta(int a, int b)
{
if(v[a].x==v[b].x)
return inf;
return (v[b].y-v[a].y)/(v[b].x-v[a].x);
};
struct cmp
{
bool operator () (const int &a, const int &b)
{
return panta(a,orig)<panta(b,orig);
}
};
inline double semn( int A, int B, int C ) {
return ( double )v[ A ].x*v[ B ].y + v[ B ].x*v[ C ].y + v[ C ].x*v[ A ].y - v[ A ].y*v[ B ].x - v[ B ].y*v[ C ].x - v[ C ].y*v[ A ].x;
}
ifstream fin("infasuratoare.in");
int main()
{
freopen("infasuratoare.out","w",stdout);
fin>>n;
orig=1;
for(i=1;i<=n;++i)
{
fin>>v[i].x >>v[i].y;
//cautam punctul cu x-ul cel mai mic...in caz de egalitate luam pnctul cu y minim
if(v[i].x<v[orig].x || (v[i].x==v[orig].x && v[i].y<v[orig].y))
{
orig=i;
}
ind[i]=i;
}
//fout<<orig<<"\n";
//sortare in functie de panta facuta cu cel mai din stanga punct
sort(ind+1,ind+n+1,cmp());
vf=1;
stiva[vf]=orig;
for( i = 1; i <= n; i++ ){
if( ind[i] != orig ) {
for( ; vf >= 2 && semn( stiva[ vf-1 ], stiva[ vf ], ind[ i ] ) < 0; --vf );
stiva[ ++vf ] = ind[ i ];
}
}
printf("%d\n",vf);
for(i=1;i<=vf;i++)
{
printf("%lf %lf\n",v[stiva[i]].x,v[stiva[i]].y);
}
}