Pagini recente » Cod sursa (job #1735160) | Cod sursa (job #2507204) | Cod sursa (job #3280423) | Cod sursa (job #760491) | Cod sursa (job #676482)
Cod sursa(job #676482)
#include <algorithm>
#include <stdio.h>
#define INF 1000000
using namespace std ;
struct punct{
float x ;
float y ;
float p ;
} ;
float panta (punct A,punct B) {
/*
(Ay-By)/(Ax-Bx)
*/
if (A.x==B.x) {
return INF ;
}
else
return (A.y-B.y)/(A.x-B.x) ;
}
int comp(punct A,punct B) {
if (A.p>B.p) return 0 ;
else return 1 ;
}
punct a[120001] ;
punct stiva[120001] ;
int cap ;
int right_turn(punct A,punct B,punct C){
float puc=(B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x) ;
if (puc<=0)return 1 ;
return 0;
}
int main() {
freopen ("infasuratoare.in","r",stdin) ;
freopen ("infasuratoare.out","w",stdout) ;
int n ;
scanf ("%d" , &n) ;
float xx , yy , tmp ;
scanf ("%f%f" , &a[1].x , &a[1].y) ;
float mx=a[1].x , my=a[1].y ;
for (int i=2 ; i<=n ; ++i) {
scanf ("%f%f" , &xx , &yy) ;
if (xx<mx) {
mx=xx ;
my=yy ;
tmp=a[1].x ;
a[1].x=xx ;
a[i].x=tmp ;
tmp=a[1].y ;
a[1].y=yy ;
a[i].y=tmp ;
}
else {
if (xx==mx) {
if (yy<my) {
mx=xx ;
my=yy ;
tmp=a[1].x ;
a[1].x=xx ;
a[i].x=tmp ;
tmp=a[1].y ;
a[1].y=yy ;
a[i].y=tmp ;
}// else yy <
else {
a[i].x=xx ;
a[i].y=yy ;
}
}//if ==
else {
a[i].x=xx ;
a[i].y=yy ;
}
}//else
}//for
a[1].p=-INF ;
for (int i=2 ; i<=n ; ++i) {
a[i].p=panta(a[i],a[1]) ;
}
sort (a+2,a+n+1,comp) ;
stiva[++cap]=a[1] ;
stiva[++cap]=a[2] ;
for (int i=3 ; i<=n ; ++i) {
if (right_turn(a[i],stiva[cap],stiva[cap-1])==1) {
stiva[++cap]=a[i] ;
}
else {
while (right_turn(a[i],stiva[cap],stiva[cap-1])==0) {
cap-=1 ;
}
stiva[++cap]=a[i] ;
}
}
printf ("%d\n" , cap) ;
for (int i=1 ; i<=cap ;++i) printf ("%f %f\n" , stiva[i].x , stiva[i].y) ;
return 0;
}