Pagini recente » Cod sursa (job #1962091) | Cod sursa (job #2099472) | Cod sursa (job #910631) | Istoria paginii runda/simulare_oni_hlo_mediu/clasament | Cod sursa (job #702340)
Cod sursa(job #702340)
#include<stdio.h>
#include<algorithm>
#define Nmax 120009
#define mp make_pair
#define x first
#define y second
#define ER 1e-12
using namespace std;
int q=1,n,i,nr,ok[Nmax],Q[Nmax];
pair<double,double> p[Nmax];
inline double abs(double x)
{
if (x<0) return -x;
return x;
}
int semn(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
double A=b.y-a.y;
double B=a.x-b.x;
double C=a.y*b.x-a.x*b.y;
if (A*c.x+B*c.y+C+ER>0) return -1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p+1,p+n+1);
nr=2;
Q[1]=1;Q[2]=2;
ok[2]=1;
i=3;
while (!ok[1])
{
while (ok[i])
{
if (i==n) q=-1;
i+=q;
}
while (nr>=2 && semn(p[Q[nr]],p[Q[nr-1]],p[i])==-1)
{
ok[Q[nr]]=0;
nr--;
}
nr++;
Q[nr]=i;
ok[i]=1;
}
nr--;
printf("%d\n",nr);
for (i=1;i<=nr;i++)
printf("%lf %lf\n",p[Q[i]].x,p[Q[i]].y);
}