Cod sursa(job #1958038)

Utilizator nick12nicolae mihalache nick12 Data 7 aprilie 2017 22:48:50
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>
using namespace std;



#define pp pair<int,int>
#define oo 100000000
#define RRR ios_base::sync_with_stdio(false);cin.tie(0);
#define ll long long
#define int ll


struct punct
{
    double x,y;
};

double crossProduct(punct A, punct B, punct C) {
    B.x-=A.x;
    B.y-=A.y;
    C.x-=A.x;
    C.y-=A.y;
    return B.x*C.y-B.y*C.x;
}

int orient(punct p, punct q, punct r)
{
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;
    return (val > 0) ? 1 : 2;
}
punct points[120000];

bool cmp(punct a, punct b) {
    return (crossProduct(points[1],a,b) < 0);
}

void convexhull(int n)
{
    if (n < 3)
        return ;
    vector <punct> hull;

    int l = 0;
    for (int i=1;i <n;i++)
        if (points[i].x < points[l].x)
            l = i;
    int p = l,q;
    do
    {
        hull.push_back(points[p]);
        q = (p+1)%n;
        for (int i= 0;i<n;i++)
        {
            if (orient(points[p],points[i],points[q]) == 2)
                q = i;
        }
        p = q;
    }while (p != l);
 std::cout << std::fixed << std::showpoint;
    cout << hull.size() << "\n";
    std::cout << std::setprecision(6);
    sort(hull.rbegin(),hull.rend(),cmp);
    for (int i=0;i<hull.size();i++)
        cout << hull[i].x << " " << hull[i].y << "\n";
}

int32_t main()
{
    RRR
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
  //  freopen("data.txt","r",stdin);
    int n;
    cin >> n;
    for (int i=0;i<n;i++)
    {
        double a,b;
        cin >> a >> b;
        points[i].x = a;
        points[i].y = b;
    }

    convexhull(n);
    return 0;
}