Cod sursa(job #1869782)

Utilizator AlexandraIrimiaAlexandra Irimia AlexandraIrimia Data 6 februarie 2017 10:10:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define ct 0.000000000001
int n,r,use[120110],k,i,pas;
int stiva[120100];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
   double x,y;
}v[120100],A,B;
int comp(punct A,punct B)
{
    return (A.y<B.y ||(A.y==B.y && A.x<B.x));
}
void coeficienti(punct A,punct B,double &aa,double &bb,double &cc)
{
    aa=A.y-B.y;
    bb=B.x-A.x;
    cc=A.x*B.y-A.y*B.x;
}
void modific()
{
    if(pas==1)
    {
        i++;
        if(i==n)pas=-1;

    }
    else i--;
}
int semn(punct A,punct B,punct C)
{
    double aa,bb,cc;
    coeficienti(A,B,aa,bb,cc);
    if(aa*C.x+bb*C.y+cc<=0) return -1;
    return 1;
}
void acoperire()
{
    double u,umin;
    sort(v+1,v+n+1,comp);
    pas=1; stiva[1]=1; stiva[2]=2;use[2]=1;
    k=2;i=2;///punctul curent
    while(i>1)
    {
        while(use[i])modific();
        if(i==0) break;
        while(k>1 && semn(v[stiva[k-1]],v[stiva[k]],v[i])==-1)
        {
            use[stiva[k]]=0;/// deselectare
            k--;///scot din stiva
        }
        k++; stiva[k]=i; use[i]=1;
    }
   g<<k-1<<endl;
    for(i=1;i<=k-1;i++){g<<fixed<<setprecision(6)<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<endl;}
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++) f>>v[i].x>>v[i].y;
    acoperire();
    return 0;
}
/*
12
1 1
11 1
11 20
1 20
4 5
1.5 6
5 5
5 2
5 8
10 16
20 5
8 45
*/