Pagini recente » Cod sursa (job #2289091) | Cod sursa (job #2722797) | Cod sursa (job #755374) | Cod sursa (job #3178235) | Cod sursa (job #753654)
Cod sursa(job #753654)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,l1,l2;
typedef pair<double,double> pdd;
pdd a[100100];
struct cmp
{
inline bool operator()(const pdd &a,const pdd &b)const
{
if(a.first==b.first)
{
return a.second<b.second;
}
return a.first<b.first;
}
};
inline int semiplan(pdd a,pdd b,pdd c)
{
if((a.first*b.second*1)+(b.first*c.second*1)+(c.first*a.second*1)>(1*b.second*c.first)+(1*c.second*a.first)+(1*a.second*b.first))
return 1;
return -1;
}
inline void make()
{
int lf=0,pas=1,i;
int stv[100100],ok[100100];
stv[++stv[0]]=1;stv[++stv[0]]=2;
i=3;
while(i>1)
{
while(ok[i])
{
i+=pas;
if(i==n)
{
pas=-1;
}
}
while(semiplan(a[stv[stv[0]-1]],a[stv[stv[0]]],a[i])==-1 && stv[0]>=2)
{
ok[stv[stv[0]--]]=0;
}
ok[i]=1;
stv[++stv[0]]=i;
}
printf("%d\n",stv[0]-1);
for(int i=1;i<=stv[0]-1;++i)
{
printf("%.6lf %.6lf\n",a[stv[i]].first,a[stv[i]].second);
}
}
int main()
{
ifstream in("infasuratoare.in");
freopen("infasuratoare.out","w",stdout);
in>>n;
for(int i=1;i<=n;++i)
{
in>>a[i].first>>a[i].second;
}
sort(a+1,a+n+1,cmp());
make();
return 0;
}