Cod sursa(job #915524)

Utilizator tudy23Coder Coder tudy23 Data 15 martie 2013 09:31:11
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
struct pct
{
    int poz;
    double x,y;
}x[100001];
const double prec=pow(10,-12);
int minn=1;
double panta[100001];
pct stiv[100001];
int cur;
int smn;
inline int semn(pct x1, pct x2, pct x3)
{
    double det = x1.x*(x2.y-x3.y)+x1.y*(x3.x-x2.x)-x3.x*x2.y+x3.y*x2.x;
    if(det>prec)
        return 1;
    if(det<-prec)
        return -1;
    if(det<prec)
        return 0;
}
bool cmp(const pct x1,const  pct x2)
{
    if(panta[x1.poz]-panta[x2.poz]>prec)
        return true;
    else if(abs(panta[x1.poz]-panta[x2.poz])<prec)
            if(x1.x-x2.x>prec)
                return true;
            else if(abs(x1.x-x2.x)<prec)
                    if(x1.y-x2.y<-prec)
                        return true;
    else return false;
}
inline double dist(int x1, int x2)
{
    return sqrt((x[x1].x-x[x2].x)*(x[x1].x-x[x2].x)+(x[x1].y-x[x2].y)*(x[x1].y-x[x2].y));
}
void citire()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf%lf",&x[i].x,&x[i].y);
        x[i].poz=i;}
    fclose(stdin);
}
void stab_pornire()
{
    for(int i=2;i<=n;++i)
        if(x[i].y-x[minn].y<-prec)
            minn=i;
        else if(abs(x[i].y-x[minn].y)<prec)
                if(x[i].x-x[minn].x<-prec)
                    minn=i;
    stiv[++cur]=x[minn];
}
void pante()
{
    for(int i=1;i<=n;++i)
        if(x[i].poz!=stiv[1].poz&&abs(x[i].y-stiv[1].y)>prec)
            panta[i]=((x[i].x-x[minn].x)/dist(minn,i));
        else if(x[i].poz!=stiv[1].poz&&abs(x[i].y-stiv[1].y)<prec){
            panta[i]=1;
            if(x[i].x>stiv[2].x)
            stiv[2]=x[i];
        }
}
void infconv()
{
    int i;
    cur=3;
    int p=0;
    for(int i=1;i<=n;++i)
        if(stiv[2].poz==x[i].poz){
            p=i;break;}
    if(p==0){
    stiv[2]=x[1];
    p=1;}
    stiv[3]=x[p+1];
    smn=semn(stiv[1],stiv[2],stiv[3]);
    for(int i=p+2;i<=n;++i)
    {
        if(x[i].poz!=stiv[1].poz){
        if(smn!=semn(stiv[cur-1],stiv[cur],x[i]))
            stiv[cur]=x[i];
        else
            stiv[++cur]=x[i];
        }
    }
}
void afisare()
{
    freopen("infasuratoare.out","w",stdout);
    printf("%d\n",cur);
    for(int i=1;i<=cur;++i)
        printf("%lf %lf\n",stiv[i].x,stiv[i].y);
}
int main()
{
    citire();
    stab_pornire();
    pante();
    sort(x+1,x+n+1,cmp);
    infconv();
    afisare();
    return 0;
}