Cod sursa(job #952738)

Utilizator deea101Andreea deea101 Data 23 mai 2013 21:30:53
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <cmath>
#define maxn 120001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct punct
{
    float x,y;

}p[maxn];

int inf[maxn];

float len(int i,int j)
{
    return sqrt((p[j].x-p[i].x)*(p[j].x-p[i].x) + (p[j].y-p[i].y)*(p[j].y-p[i].y));
}

float angle(int i, int j, int k)
{
    float unghi,a1,a2,b1,b2,l1,l2;
    a1=p[j].x-p[i].x;
    b1=p[j].y-p[i].y;
    a2=p[k].x-p[i].x;
    b2=p[k].y-p[i].y;

    l1=len(i,j);
    l2=len(i,k);

    unghi=acos((a1*a2+b1*b2)/(l1*l2))*(180/M_PI);
    if(unghi<0) unghi=unghi+2*M_PI;
    return unghi;
}

int main()
{
    f>>n;
    int i,mini;
    for(i=1;i<=n;i++)
        f>>p[i].x>>p[i].y;

    mini=1;
    for(i=1;i<=n;i++)
    {
        if(p[i].x<p[mini].x) mini=i;
        else if(p[i].x==p[mini].x)
            if(p[i].y<p[mini].y) mini=i;
    }


    p[0].x=p[mini].x;
    p[0].y=p[mini].y-1;

    int k=1;
    int unghi,curr=mini; int prec=0;
    int maxu,wini;

    do
    {
        inf[k++]=curr;
        maxu=-1; wini;
        for(i=1;i<=n;i++)
        {
            if(i==curr || i==prec) continue;
            unghi=angle(curr,i,prec);
            if(maxu<unghi) {maxu=unghi; wini=i;}

        }
        prec=curr;
        curr=wini;

    }while(curr!=mini);

    g<<k-1<<'\n';
    for(i=k-1;i;i--)
    {
        g<<p[inf[i]].x<<' '<<p[inf[i]].y<<'\n';
    }
}