Cod sursa(job #2199909)

Utilizator lorena1999Marginean Lorena lorena1999 Data 29 aprilie 2018 15:43:37
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.95 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <stack>

#define PI 3.14159265359

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct pct{ double x, y;};

stack < pct > s;

pct lwst;

void read(int &n, pct v[])
    {
        lwst.x=lwst.y=(1<<30);
        f>>n;
        for(int i=1; i<=n; i++)
        {
            f>>v[i].x>>v[i].y;
            if(v[i].y<lwst.y)
                lwst=v[i];
            else if(v[i].y==lwst.y && v[i].x<lwst.x)
                lwst=v[i];
        }
    }

double angle(pct a, pct b)
    {
        if(a.x==b.x && a.y==b.y)
            return 0;
        if(b.x==a.x)
            return 90;
        double rad = abs(atan(abs((b.y-a.y)/(b.x-a.x))));
        double rez=abs(180*rad/PI);
        if(a.x<b.x)
            return 90-rez+90;
        else return rez;
    }

long double det(pct a, pct b, pct c)
    {
        return (a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-b.x*a.y-a.x*c.y);
        //return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    }

bool cond(const pct &a, const pct &b)
    {
        double ang1=angle(a, lwst);
        double ang2=angle(b, lwst);
        return (ang1<ang2);
    }

void afis()
    {
        if(!s.empty())
        {
            pct a = s.top();
            s.pop();
            afis();
            g<<setprecision(6)<<fixed<<a.x<<" "<<a.y<<'\n';
        }
    }

void convex_hull(pct v[], int n)
    {
        s.push(lwst);
        s.push(v[2]);
        int idx=3;
        pct a=lwst, b=v[2], c;
        while(idx<=n)
        {
            long double d = det(a, b, v[idx]);
            if(d>0)
            {
                s.push(v[idx]);
                a=b;
                b=v[idx];
            }
            else
            {
                b=a;
                s.pop();
                s.pop();
                a=s.top();
                d=det(a, b, v[idx]);
                while(d<0)
                {
                    b=a;
                    s.pop();
                    a=s.top();
                    d=det(a, b, v[idx]);
                }
                s.push(b);
                s.push(v[idx]);
                a=b;
                b=v[idx];
            }
            idx++;
        }
        g<<s.size()<<'\n';
    }

int main()
    {
        int n;
        pct v[100001];
        read(n, v);

        sort(v+1, v+n+1, cond);
        /*for(int i=1; i<=n; i++)
            cout<<v[i].x<<" "<<v[i].y<<" "<<angle(v[i], lwst)<<'\n';
        cout<<lwst.x<<" "<<lwst.y<<'\n'<<'\n';
        cout<<'\n'<<'\n';
        for(int i=1; i<=n; i++)
            cout<<v[i].x<<" "<<v[i].y<<'\n';
        cout<<'\n';
        cout<<v[5].x<<" "<<v[5].y<<" "<<v[7].x<<" "<<v[7].y<<" "<<v[8].x<<" "<<v[8].y<<endl;
        cout<<det(v[5], v[7], v[8])<<"IVI";
        cout<<'\n';*/
        convex_hull(v, n);
        afis();
    }