Cod sursa(job #840035)

Utilizator andreea29Iorga Andreea andreea29 Data 22 decembrie 2012 12:58:48
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include<fstream>
#include<algorithm>
#include<cmath>
 
#define Nmax 120010
#define Num 10000000
 
using namespace std;
 
int n, st[Nmax], viz[Nmax], k;
 
struct punct 
{
    float x;
    float y;
} p[Nmax];
 
int cmp (punct a, punct b)
{
    if (a.x > b.x || (a.x == b.x && a.y > b.y))
        return 0;
    return 1;
}
 
float dist (punct a, punct b)
{
    return sqrt (double ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}
 
float det (punct a, punct b, punct c)
{
    return (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}
 
int semn (punct a, punct b, punct c)
{
    float d = det (a, b, c);
    if (d > 0)
        return 1;
    else
        if (d < 0)
            return 2;
        else
            return 0;
}
 
void convex ()
{
    st[0] = 0;
    st[1] = 1;
    st[2] = 2;
    viz[1] = viz[2] = 1;
    int s = semn (p[0], p[1], p[2]);
    k = 2;
    int i = 3;
    while (i < n)
    {
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            viz[st[k]] = 0;
            --k;
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
        ++k;
        st[k] = i;
        viz[i] = 1;
        ++i;
    }
    --i;
    while (i >= 0)
    {
        while (viz[i] && i >= 0)
            --i;
		if (i < 0)
			break;
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            --k;
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
		++k;
		st[k] = i;
		--i;
    }
}
 
int main()
{
    ifstream f("infasuratoare.in");
    ofstream h("infasuratoare.out");
    f >> n;
    for (int i = 0; i < n; ++i)
        f >> p[i].x >> p[i].y;
    f.close();
    sort (p, p + n, cmp);
     
//  for (int i = 0; i < n; ++i)
//      h << p[i].x << " " << p[i].y << '\n';
//  h << '\n'<< '\n';
     
    convex ();
     
    h << k << '\n';
    for (int i = 0; i < k; ++i)
    {
        long long am = p[st[i]].x * Num;
        h << double (am / Num);
        h << " ";
        am = p[st[i]].y * Num;
        h << double (am / Num);
        h << '\n';
        //h << p[st[i]].x << " " << p[st[i]].y << '\n';
    }
    h.close();
    return 0;
}