Pagini recente » Cod sursa (job #2963980) | Cod sursa (job #3135518) | Cod sursa (job #2245097) | Cod sursa (job #3237405) | Cod sursa (job #2183879)
#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;
}