Pagini recente » Cod sursa (job #3123360) | Borderou de evaluare (job #1918936) | Cod sursa (job #607625)
Cod sursa(job #607625)
#include <cstdio>
#include <algorithm>
using namespace std;
class vect {
public:
float x,y;
vect():x(0.0f),y(0.0f) {}
vect(int X,int Y):x(X),y(Y) {}
const int operator<(const vect& aux) const{
if(x * aux.y - y * aux.x >=0.0f) return 1;
if(x * aux.y - y * aux.x < 0.0f) return 0;
}
vect operator-(const vect& aux) const {
return vect( x - aux.x , y - aux.y );
}
};
#define NMAX 120005
vect vects[NMAX] , st[NMAX];
int n,k,p = 1;
int cmp(const vect& p1, const vect& p2) {
vect p11 = p1 - vects[0];
vect p22 = p2 - vects[0];
if(p11.x * p22.y - p11.y * p22.x >=0.0f) return 1;
if(p11.x * p22.y - p11.y * p22.x < 0.0f) return 0;
}
int main() {
freopen("infasuratoare.in" , "r" , stdin );
freopen("infasuratoare.out", "w" , stdout);
scanf("%d",&n);
for( int i = 0 ; i < n ; i++ )
scanf("%f %f" , &vects[i].x , &vects[i].y );
int ind = 0;
for(int i = 1 ; i < n ; i++) {
if(vects[i].y < vects[ind].y) ind = i;
if(vects[i].y == vects[ind].y && vects[i].x < vects[ind].x) ind = i ;
}
swap(vects[ind], vects[0]);
sort(vects +1 , vects + n,cmp);
k = 0; st[k] = vects[0];
k = 1; st[k] = vects[1];
for(int i = 1 ; i < n ; i++ ) {
while( ( k > 0 ) && !( (st[k] - st[k-1]) < (vects[i] - st[k]) ) ) k--;
st[++k] = vects[i];
}
printf("%d\n",k+1);
for(int i =0 ; i <= k ; i++ )
printf("%f %f\n", st[i].x , st[i].y );
return 0;
}