Cod sursa(job #2557330)

Utilizator TudorChirila11Tudor Chirila TudorChirila11 Data 25 februarie 2020 18:55:23
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define N 120005
#define PI 3.1415926535897932384626433832795
using namespace std;
typedef long long ll;
ll n, i, j, xmin, ymin, k, pz;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct frac
{
    long double x, y;
    int p;
}f[N];
struct punct
{
    long double x, y;
}p[N], st[N];
bool comp(frac a, frac b)
{
    return a.x<b.x;
}
long double arie(punct a, punct b, punct c)
{
    long double m[3][3]={{a.x,a.y,1},{b.x,b.y,1},{c.x,c.y,1}};
    return (m[0][0]*m[1][1]*m[2][2] + m[0][1]*m[1][2]*m[2][0]+m[0][2]*m[1][0]*m[2][1])-
            (m[0][2]*m[1][1]*m[2][0]+m[2][1]*m[1][2]*m[0][0]+m[2][2]*m[1][0]*m[0][1]);
}
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
}
int main()
{
    fast();
    fin>>n;
    ymin=2000000000;
    for(i=1;i<=n;++i)
        {
            fin>>p[i].x>>p[i].y;
            if(p[i].y<ymin||(p[i].y==ymin&&p[i].x>xmin))
            {
                xmin=p[i].x;
                ymin=p[i].y;
                pz=i;
            }
        }
   // swap(p[pz],p[n]);
   // --n;
    for(i=1;i<=n;++i)
        if(i!=pz)
    {
        f[i].p=i;
        ll Dx=+p[i].x-p[pz].x;
        ll Dy=+p[i].y-p[pz].y;
        f[i].x=abs(Dy);
        f[i].y=abs(Dx);
        if(f[i].y==0)
            {
                //if(Dx>0)
                f[i].x=90;
                //else f[i].x=270;
                continue;
            }
        else
        f[i].x=atan(f[i].x/f[i].y)*180/PI;
        if(Dx<0&&Dy<0)
            f[i].x+=180;
        else if(Dx<0)
            f[i].x=180-f[i].x;
        else if(Dy<0)f[i].x=360-f[i].x;
    }
    for(i=1;i<=n;++i)
            cout<<f[i].x<<' '<<p[i].x<<' '<<p[i].y<<'\n';
    //cout<<pz;
    swap(f[pz],f[n]);
    --n;
    sort(f+1,f+n+1,comp);
    for(i=1;i<=n;++i)
        cout<<p[f[i].p].x<<' '<<p[f[i].p].y<<'\n';
    ++k;
  //  f[n+1].p=pz;
    st[k]=p[pz];
   // cerr<<st[k].x<<' '<<st[k].y<<'\n';
    ++k;
    st[k]=p[f[1].p];
    //cerr<<st[k].x<<' '<<st[k].y<<'\n'<<'\n';
    for(i=2;i<=n;++i)
    {
        while(k>1&&arie(st[k-1],st[k],p[f[i].p])<=0)
            --k;
        st[++k]=p[f[i].p];
      //  cout<<st[k].x<<' '<<st[k].y<<'\n';
    }
    fout<<k<<'\n';
    for(i=1;i<=k;++i)
        fout<<fixed<<setprecision(10)<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}