Cod sursa(job #2183878)

Utilizator raduqRadu Minea raduq Data 23 martie 2018 15:35:42
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
using namespace std;
struct gigel
{
    double x, y;
};
gigel v[120001], vs[6001], vd[6001] ;
int n, i, j, ks, kd, k, k1;
double det;
bool cmp( gigel a, gigel b )
{
    if ( a.y < b.y ) return true;
    if ( a.y == b.y ) if( a.x < b.x ) return true;
    return false;
}
void parte( int k, double xa, double ya, double xb, double yb, double xc, double yc )
{
  double det=xa*xb+xb*yc+xc*ya-xc*yb-xb*ya-xa*yc;
  if (det<0)
  { ks++; vs[ks]=v[k]; }
  else
  { kd++; vd[kd]=v[k]; }
}
void solutie(gigel vx[120001], double kx)
{
  for( i=1; i<=kx; i++)
    {
      k++;
      v[k]=vx[i];
      for( j=1; j<k; j++ )
      {
        if(kx==kd)
        { if(v[j].x + v[j].y > v[i].x + v[i].y) k--; }
        else if(v[j].x + v[j].y < v[i].x + v[i].y) k--;
      }
    }
}
int main()
{
    freopen( "infasuratoare.in", "r", stdin);
    freopen( "infasuratoare.out", "w", stdout);
    cin >> n;
    for ( i=1; i<=n; i++ ) { cin >> v[i].x >> v[i].y; }
    sort ( v+1, v+n+1, cmp );
    for( i=2; i<n; i++) parte(i, v[1].x, v[1].y, v[n].x, v[n].y, v[i].x, v[i].y);
    k=1;
    for( i=1; i<=ks; i++)
    {
      k++;
      v[k]=vs[i];
      for( j=1; j<k; j++ )
      { if(v[j].x < v[i].x) k--; }
    }
    k1=k;
    for( i=1; i<=kd; i++)
    {
      k1++;
      v[k1]=vd[i];
      for( j=k+1; j<k1; j++ )
      { if(v[j].x > v[i].x) k1--; }
    }
    cout << k1+1 << '\n';
    for( i=1; i<=k; i++) cout << fixed << setprecision(6) << v[i].x << " " << v[i].y << '\n';
    cout<< fixed << setprecision(6) << v[n].x << " " << v[n].y << '\n';
    for( i=k1; i>=k+1; i--) cout << fixed << setprecision(6) << v[i].x << " " << v[i].y << '\n';

    ///ba fa o ma sa arate bn
    return 0;
}