Pagini recente » Cod sursa (job #2823376) | Cod sursa (job #1632579) | Cod sursa (job #781524) | Cod sursa (job #2868104) | Cod sursa (job #554795)
Cod sursa(job #554795)
#include <algorithm>
using namespace std;
#define sc second
#define fs first
#define INF 0x3f3f3f3f
#define DIM 120005
pair <double,double> v[DIM];
int ind[DIM],st[DIM];
int N,vf,orig;
inline double panta (int a,int b)
{
if (v[a].fs==v[b].fs)
return INF;
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 (a,orig)<panta (b,orig);
}
};
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[orig].fs || (v[i].fs==v[orig].fs && v[i].sc<v[orig].sc))
orig=i;
ind[i]=i;
}
}
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]=orig;
for (i=1; i<=N; ++i)
if (ind[i]!=orig)
{
for ( ; vf>=2 && det (st[vf-1],st[vf],ind[i])<0; --vf);
st[++vf]=ind[i];
}
printf ("%d\n",vf);
for (i=1; i<=vf; ++i)
printf ("%lf %lf\n",v[st[i]].fs,v[st[i]].sc);
}
int main ()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
read ();
solve ();
return 0;
}