Pagini recente » Cod sursa (job #542297) | Cod sursa (job #2631636) | Cod sursa (job #2946670) | Istoria paginii runda/cerculdeinfo-lectiile9_10_11_12_13 | Cod sursa (job #779985)
Cod sursa(job #779985)
#include <stdio.h>
#include <algorithm>
#define NMax 120010
using namespace std;
const char IN[]="infasuratoare.in",OUT[]="infasuratoare.out";
struct point{
double x;
double y;
bool operator<(point const &b) const{
return x<b.x || x==b.x && y<b.y;
}
} P[NMax] , H[NMax];
int N,L;
double cross(point const &A,point const &B,point const &C){
return (A.x*(B.y-C.y) + B.x*(C.y-A.y) + C.x*(A.y-B.y))*0.5;
}
void convex(){
int i,l;
sort(P+1,P+N+1);
for (i=1;i<=N;++i){
while (L>1 && cross(H[L-1],H[L],P[i])<=0)
--L;
H[++L]=P[i];
}
l=L;
for (i=N;i>0;--i){
while (L>l && cross(H[L-1],H[L],P[i])<=0)
--L;
H[++L]=P[i];
}
--L;
}
int main()
{
int i;
freopen(IN,"r",stdin);
scanf("%d",&N);
for (i=1;i<=N;++i) scanf("%lf%lf",&P[i].x,&P[i].y);
fclose(stdin);
convex();
freopen(OUT,"w",stdout);
printf("%d\n",L);
for (i=1;i<=L;++i) printf("%lf %lf\n",H[i].x,H[i].y);
fclose(stdout);
return 0;
}