Pagini recente » Cod sursa (job #490540) | Cod sursa (job #284149) | Cod sursa (job #3257898) | Cod sursa (job #1919114) | Cod sursa (job #2835634)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int dim=120009;
struct punct{
long double x,y;}v[dim];
punct stiva[dim];
int vf;
long double determinat(punct A,punct B,punct C){
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
bool ccw(punct A,punct B,punct C){
return determinat(A,B,C)>0;
}
bool cmp(punct A,punct B){
return ccw(v[1],A,B);
}
signed main(){
int n;
fin>>n;
for(int i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
if(v[1].y==v[i].y){
if(v[1].x>v[1].x)
swap(v[1],v[i]);
}
else{
if(v[1].y>v[i].y)
swap(v[1],v[i]);
}
}
sort(v+2,v+n+1,cmp);
stiva[++vf]=v[1];
for(int i=2;i<=n;i++){
while(vf>1&&!ccw(stiva[vf-1],stiva[vf],v[i])){
vf--;
}
stiva[++vf]=v[i];
}
fout<<vf<<'\n';
for(int i=1;i<=vf;i++)
fout<<fixed<<setprecision(12)<<stiva[i].x<<' '<<stiva[i].y<<'\n';
}