Cod sursa(job #2468935)

Utilizator cyg_andrei_HHendoreanu Andrei Sebastian cyg_andrei_H Data 6 octombrie 2019 11:50:16
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct Point
{
    double x,y;
};
const int NMAX=120000;
vector <Point> r;
Point v[NMAX+5];
bool cmp_y(Point a,Point b)
{
    return a.y<b.y;
}
bool cmp_orar(Point a,Point b)
{
    return atan2(a.y-v[1].y,a.x-v[1].x)<atan2(b.y-v[1].y,b.x-v[1].x);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    Point temp1,temp2,temp3;
    int n,i,m1,m2;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp_y);
    sort(v+2,v+n+1,cmp_orar);
    r.push_back(v[1]);
    r.push_back(v[2]);
    for(i=3;i<=n;++i)
    {
        //r.push_back(v[i]);
        temp2=*(r.end()-1);
        temp1=*(r.end()-2);
        temp3=v[i];
        m1=(temp2.y-temp1.y)*(temp3.x-temp2.x);
        m2=(temp2.x-temp1.x)*(temp3.y-temp2.y);
        while(m1>m2)
        {
            r.pop_back();
            temp2=*(r.end()-1);
            temp1=*(r.end()-2);
            m1=(temp2.y-temp1.y)*(temp3.x-temp2.x);
            m2=(temp2.x-temp1.x)*(temp3.y-temp2.y);
        }
        r.push_back(v[i]);
    }
    printf("%d\n",r.size());
    for(i=0;i<r.size();++i)
        printf("%lf %lf\n",r[i].x,r[i].y);
    return 0;
}