Pagini recente » Cod sursa (job #2317080) | Cod sursa (job #758992) | Cod sursa (job #276415) | Cod sursa (job #2521129) | Cod sursa (job #526856)
Cod sursa(job #526856)
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define DIM 120005
#define sc second
#define fs first
pair <double,double> v[DIM];
int ind[DIM],st[DIM];
int n,o,vf;
void read ()
{
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
{
scanf ("%lf%lf",&v[i].fs,&v[i].sc);
if (i==1 || v[i].fs<v[o].fs || (v[i].fs==v[o].fs && v[i].sc<v[o].sc))
o=i;
ind[i]=i;
}
}
inline double panta (int a,int b)
{
if (v[a].fs==v[b].fs)
return INF;
else
return (v[a].sc-v[b].sc)/(v[a].fs-v[b].fs);
}
struct cmp
{
bool operator () (const int &a,const int &b)
{
return panta (o,a)>panta (o,b);
}
};
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 ()
{
int i;
sort (ind+1,ind+n+1,cmp ());
st[++vf]=o;
for (i=1; i<=n; ++i)
if (ind[i]!=o)
{
for ( ; vf>=2 && det (st[vf-1],st[vf],ind[i])>0; --vf);
st[++vf]=ind[i];
}
}
void print ()
{
int i;
printf ("%d\n",vf);
for (i=vf; i>=1; --i)
printf ("%.6lf %.6lf\n",v[st[i]].fs,v[st[i]].sc);
}
int main ()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
read ();
solve ();
print ();
return 0;
}