Cod sursa(job #2500721)

Utilizator daniel96Daniel Dan daniel96 Data 28 noiembrie 2019 16:11:28
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <deque>
#include <algorithm>
using namespace std;
const int nm=120000;
struct nod{long double x,y,u;}pct[nm];
bool u[nm];
long double xc,yc;
int i,n,p,ul,aul;
int f(nod a, nod b)
{
    return a.u>b.u;
}
deque<int>co;
double tri(int i, int j, int k)
{
    return pct[i].x*pct[j].y+pct[j].x*pct[k].y+pct[i].y*pct[k].x-pct[j].y*pct[k].x-pct[i].y*pct[j].x-pct[i].x*pct[k].y;
}
int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fin>>n;
    for(i=1;i<=n;i++){fin>>pct[i].x>>pct[i].y;xc+=pct[i].x;yc+=pct[i].y;}
    xc/=n;yc/=n;
    for(i=1;i<=n;i++)pct[i].u=atan2((xc-pct[i].x),(yc-pct[i].y));
    sort(pct+1,pct+n+1,f);

    p=1;
    for(i=1;i<=n;i++)
        if((pct[p].y>pct[i].y)||((pct[p].y==pct[i].y)&&(pct[p].x>pct[i].x)))p=i;
    for(i=1;i<p;i++)pct[n+i]=pct[i];
    for(i=1;i<=n;i++)pct[i]=pct[p+i-1];

    co.push_back(1);
    co.push_back(2);
    p=3;
    while(p<=n)
    {
        ul=co.back();co.pop_back();
        aul=co.back();
        if(tri(aul,ul,p)>=0){co.push_back(ul);co.push_back(p);}
         else
         {
             while(tri(aul,ul,p)<0&&(aul!=1))
             {
                 ul=aul;
                 aul=co.back();co.pop_back();
             };
            co.push_back(p);
         }
        p++;
    }
    fout<<co.size()<<"\n";
    while(!co.empty()){  p=co.front();fout<<pct[p].x<<" "<<pct[p].y<<"\n";co.pop_front();}
    return 0;
}