Cod sursa(job #893234)

Utilizator stef1995mmarcu stefan ovidiu stef1995m Data 26 februarie 2013 14:07:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
FILE *f=fopen("infasuratoare.in","r"),*g=fopen("infasuratoare.out","w");
//FILE *f=fopen("convex.in","r"),*g=fopen("convex.out","w");

struct type
{
    double tan,x,y;
};
const int maxn=120006,inf=2000000000;
type punct[maxn];
int n,i,poz,ind[maxn];
double p0x,p0y;
vector <int> sol;

bool cmp(int a,int b)
{
    double x=punct[a].tan,y=punct[b].tan;
    if(x<y)
        return true;
    return false;
}

double unghi( type a)
{
    double u=a.x-p0x,v=a.y-p0y;
    return double(atan(v/u));
}

void read()
{
    fscanf(f,"%d",&n);
    p0x=p0y=inf;
    for(i=1;i<=n; i++)
    {
        fscanf(f,"%lf%lf",&punct[i].x,&punct[i].y);
        ind[i]=i;
        if(punct[i].x<p0x || (punct[i].x==p0x && punct[i].y<p0y) )
        {
            p0x=punct[i].x;
            p0y=punct[i].y;
            poz=i;
        }
    }
    punct[poz].tan=-inf;
    for(i=1;i<=n;i++)
        if(i!=poz)
            punct[i].tan=unghi(punct[i]);
    sort( ind+1 , ind+n+1 , cmp );
}

long double deter( int i , int j , int k )
{
    long double val;
    val = (punct[i].x*punct[j].y) + (punct[j].x*punct[k].y) + (punct[k].x*punct[i].y);
    val -= ( (punct[k].x*punct[j].y) + (punct[j].x*punct[i].y) + (punct[i].x*punct[k].y) );
    return val;
}

void write()
{
    fprintf(g,"%d\n",sol.size());
    for(i=0;i<sol.size();i++)
        fprintf(g,"%lf %lf\n",punct[sol[i]].x,punct[sol[i]].y);
}

int main()
{
    read();
    sol.push_back(poz);
    sol.push_back(ind[2]);
    sol.push_back(ind[3]);
    for(i=4;i<=n;i++)
    {
        while(deter(sol[sol.size()-2],sol[sol.size()-1],ind[i])<0)
            sol.pop_back();
        sol.push_back(ind[i]);
    }
    write();
    return 0;
}