Cod sursa(job #1114536)

Utilizator StefansebiStefan Sebastian Stefansebi Data 21 februarie 2014 18:56:52
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<iostream>
#include<cmath>
#include<algorithm>
#include<fstream>
#include<iomanip>
#define PI 3.14159265
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct {
    double x; double y;
};
struct segment {
    punct a; punct b;
};
punct p0, p1, p2, p3, p4, p[120000], s[120000];
int n;
int varf;

int prod(punct p1, punct p2, punct p3){
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

void afis(){
    int i; fout << fixed;
    fout << varf << '\n';
    for (i = varf; i >= 1; i--)
        fout << setprecision(6) << s[i].x << " " << s[i].y << '\n';
}

void afisn(){
    int i;
    fout << n << '\n';
    for (i = 1; i <= n; i++)
        fout  << p[i].x << " " << p[i].y << '\n';
}

int cmp(punct p1, punct p2) {
    return prod(p[1], p1, p2) < 0;
}

void infas(){
    int i, j; int poz = 1;
    for (i = 1; i <= n; i++){
        if (p[poz].x > p[i].x)
            poz = i;
    }
    for (i = 1; i <= n; i++)
        if (p[poz].x == p[i].x and p[poz].y > p[i].y)
            poz = i;
    punct aux = p[1]; p[1] = p[poz]; p[poz] = aux;
    for (i = 2; i < n; i++)
        for (j = i + 1; j <= n; j++)
            if (prod(p[1], p[i], p[j]) > 0) {
                aux = p[i]; p[i] = p[j]; p[j] = aux;
            }
   // afisn();
    varf = 2; s[1] = p[1]; s[2] = p[2];
    for (int i = 3; i <= n; ++i) {
        while (varf >= 2 && prod(s[varf - 1], s[varf], p[i]) > 0)
            --varf;
        s[++varf] = p[i];
    }
    afis();
}

int main() {
    fin >> n; int i;
    for (i = 1; i <= n; i++)
        fin >> p[i].x >> p[i].y;
    infas();
}