Cod sursa(job #1134590)

Utilizator cypry97Dascalitei Ciprian cypry97 Data 6 martie 2014 19:30:46
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.14 kb
#include <iostream>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

struct punct
{
    double x,y;
    double u;
};

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int n;
punct p[120010];
int pos;
punct pmin;
double x,y;
int nr;
int st[120010];

bool cmp(punct a, punct b)
{
    return a.u>b.u;
}

void citire()
{
    int i;
    in>>n;
    in>>p[1].x>>p[1].y;
    pmin=p[1];
    pos=1;
    x=p[1].x;
    y=p[1].y;
    for(i=2;i<=n;i++)
    {
        in>>p[i].x>>p[i].y;
        /*if(p[i].x<=pmin.x)
        {
            if(p[i].x<pmin.x)
            {
                pmin=p[i];
                pos=i;
            }
            else if(p[i].y<pmin.y)
            {
                pmin=p[i];
                pos=i;
            }
        }*/
        if(p[i].x<x)
            x=p[i].x;
        if(p[i].y<y)
            y=p[i].y;
        if(p[i].x<=pmin.x)
            if(p[i].x<pmin.x||p[i].y<pmin.y)
            {
                pmin=p[i];
                pos=i;
            }
    }
    p[pos]=p[n];
    p[n]=pmin;
    x--;
    y--;
    for(i=1;i<=n;i++)
    {
        p[i].x-=x;
        p[i].y-=y;
        p[i].u=atan2(p[i].y,p[i].x);
    }
    sort(p+1,p+n,cmp);
    /*for(i=1;i<=n;i++)
        out<<p[i].x<<' '<<p[i].y<<' '<<p[i].u<<'\n';*/
}

double det(punct a, punct b, punct c)
{
    /*
    |xa ya 1|
    |xb yb 1| = D
    |xc yc 1|
    */
    double D=0;
    D=(a.x*b.y)+(b.x*c.y)+(c.x*a.y)-(b.y*c.x)-(c.y*a.x)-(a.y*b.x);
    return D;
}

void infasuratoare()
{
    st[1]=n;
    st[2]=1;
    int i,k=2;
    for(i=2;i<n;i++)
    {
        while(det(p[st[k-1]],p[i],p[st[k]])<0)
            k--;
        k++;
        st[k]=i;
    }
    out<<k<<'\n';
    out<<fixed<<setprecision(6);
    for(i=k;i;i--)
        out/*<<setprecision(6)*/<<p[st[i]].x+x<<' '<<p[st[i]].y+y<<'\n';
}

void test()
{
    p[1].x=0;
    p[1].y=2;
    p[2].x=2;
    p[2].y=0;
    p[3].x=0;
    p[3].y=0;
    cout<<det(p[1],p[2],p[3]);
}

int main()
{
    citire();
    infasuratoare();
    //test();
    return 0;
}