Cod sursa(job #728687)

Utilizator dacyanMujdar Dacian dacyan Data 28 martie 2012 21:26:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define DIM 121000
using namespace std;

int n, k;
pair<double ,double> P[DIM];
int pas, i;

int S[DIM]; // stiva
bool s[DIM];
void Read();
void Write();
void Hill();


void GasestePunct();
int Semn(pair<double, double>, pair<double, double>,pair<double, double>);
bool Calc(pair<double, double>, pair<double, double>);

int main()
{
    Read();
    Hill();
    Write();
    return 0;
}

void Read()
{
    ifstream fin("infasuratoare.in");
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> P[i].first >> P[i].second;
    fin.close();
}

void Hill()
{
    sort(P + 1, P + n + 1, Calc); // sortam dupa abscisa (ordonata in caz de egalitate)
    s[2] = true; 
    S[1] = 1; S[2] = 2; // punem in stiva primele 2 puncte
    
    pas = 1;
    i = 2; // pozitia in sirul curent
    k = 2; // varful stivei
    while (i > 1) 
    {
       
        GasestePunct(); // i indica punct neselectat
        if (!i) break;
        while ((k > 1) && Semn(P[S[k-1]], P[S[k]], P[i]) == -1) // == unghiul dintre [A,B] si P[i] este > 180
        {
            s[S[k]] = 0;
            k--;
        }
        k++;
        s[i] = 1;
        S[k] = i;
    }
   
  
}

void GasestePunct()
{ 
    while (s[i])
    {
        i += pas;
        if (i == n) pas = -1;
    }
}

int Semn(pair<double, double> A , pair<double, double> B ,pair<double, double> C)
{
    double aa = A.second - B.second;
    double bb = B.first - A.first;
    double cc = A.first * B.second - A.second * B.first;
    
    if ((aa * C.first + bb * C.second + cc) < 0)
        return -1;
    return 1;
}

bool Calc(pair<double, double> A , pair<double, double> B)
{
    return A.second < B.second || (A.second == B.second && A.first < B.first);
}    

void Write()
{
    ofstream fout("infasuratoare.out");
    fout << k-1 << '\n';
    for (int i = 1; i < k; ++i)
    {
       fout << fixed << setprecision(6) << P[S[i]].first;
       fout << ' ' << fixed << setprecision(6) << P[S[i]].second << '\n';
    }   
    fout.close();
}