Cod sursa(job #2199914)

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

#define PI 3.14159265359

using namespace std;

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

struct pct{ double x, y;};

pct sol[120001];

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 (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 convex_hull(pct v[], int n)
    {
        int u=0;
        sol[++u]=v[1];
        sol[++u]=v[2];
        for(int i=3; i<=n; i++)
        {
            while(u>1 && det(sol[u-1], sol[u], v[i])<0)
                u--;
            sol[++u]=v[i];
        }
        g<<u<<'\n';
        for(int i=1; i<=u; i++)
            g<<setprecision(6)<<fixed<<sol[i].x<<" "<<sol[i].y<<'\n';
    }

int main()
    {
        int n;
        pct v[120001];
        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);
    }