Cod sursa(job #1920683)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 10 martie 2017 09:16:47
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;
#define eps 0.000000000001
int st[120005],n,i,nr,ap[120005];
struct punct
{
    double x,y;
}a[120005];
double modul(double x)
{
    if(x<0)return -x;
    return x;
}
bool egal(double x, double y)
{
    if(modul(x-y)<=eps)return 1;
    return 0;
}
bool cmp(punct a, punct b)
{
    if(egal(a.x,b.x))return a.y<b.y;
    return a.x<b.x;
}
/**
ax ay 1
bx by 1
cx cy 1
**/
double det(punct A, punct B, punct C)
{
  ///  return (double) A.x*B.y + B.x*C.y + C.x*A.y - C.x*B.y - B.x*A.y - A.x*C.y;
  return (double) A.x*B.y+B.x*C.y+A.y-C.x*B.y-A.y*B.x-C.y;
}
void elimin(int i)
{
    while(nr>=2&&det(a[st[nr-1]],a[st[i]],a[i])<eps)
    {
        ap[st[nr]]=0;
        nr--;
    }
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    nr=2;
    st[1]=1;
    st[2]=2;
    ap[2]=1;
    for(i=3;i<=n;i++)
    {
        elimin(i);
        nr++;
        st[nr]=i;
        ap[i]=1;
    }
    for(i=n;i>1;i--)
    {
        if(ap[i]==0)
        {
            elimin(i);
            nr++;
            st[nr]=i;
            ap[i]=1;
        }
    }
    elimin(1);
    printf("%d\n",nr);
    for(i=1;i<=nr;i++)
    {
        printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
    }
    return 0;
}