Cod sursa(job #2327263)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 24 ianuarie 2019 16:06:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define Dim 120007
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N,poz,ST[Dim],head;
typedef struct { double x,y; } Point;
double det(Point,Point);
Point V[Dim];

double det(Point A,Point B,Point C)
{
    return (A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x);
}

bool cmp(Point a,Point b)
{
    return det(a,b,V[1])<0;
}

int main()
{
    f>>N;
    for(int i=1;i<=N;i++)
    {
        f>>V[i].x>>V[i].y;
        if(i==1) poz=1;
        else
        if(V[i].y<V[poz].y) poz=i;
        else
        if(V[i].y==V[poz].y&&V[i].x<V[poz].x) poz=i;
    }
    swap(V[1],V[poz]);
    sort(V+2,V+N+1,cmp);
    ST[1]=1;
    ST[2]=2;
    head=2;
    for(int i=3;i<=N;i++)
    {
        while(head>=2&&det(V[i],V[ST[head-1]],V[ST[head]])>0)
            head--;
        ST[++head]=i;
    }
    g<<head<<'\n';
    g<<setprecision(9)<<fixed<<V[ST[1]].x<<" "<<V[ST[1]].y<<'\n';
    for(int i=head;i>1;i--)
        g<<setprecision(9)<<fixed<<V[ST[i]].x<<" "<<V[ST[i]].y<<'\n';
    return 0;
}