Pagini recente » Profil Georgiana1904 | Cod sursa (job #1296959) | Cod sursa (job #1608596) | Cod sursa (job #1640288) | Cod sursa (job #1387954)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x;
double y;
}P[DIM],first,S[DIM];
int pos,top,N;
double det(const point p1,const point p2,const point p3){
return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
int cmp(point p1,point p2){
return det(P[1],p1,p2)>0;
}
int main(){
fin>>N;
fin>>P[1].x>>P[1].y;
first=P[1];
pos=1;
for(int i=2;i<=N;i++){
fin>>P[i].x>>P[i].y;
if(P[i].y<first.y || (P[i].y==first.y && P[i].x<first.x))
first=P[i],pos=i;
}
swap(P[1],P[pos]);
sort(P+2,P+N+1,cmp);
S[1]=P[1];
S[2]=P[2];
top=2;
for(int i=3;i<=N;i++){
while(top>=2 && det(S[top-1],S[top],P[i])<0)
top--;
S[++top]=P[i];
}
fout<<top<<"\n";
for(int i=1;i<=top;i++)
fout<<setprecision(6)<<fixed<<S[i].x<<" "<<setprecision(6)<<fixed<<S[i].y<<"\n";
}