Pagini recente » Cod sursa (job #1886655) | Cod sursa (job #1215917) | Borderou de evaluare (job #1547912) | Cod sursa (job #670002) | Cod sursa (job #3336099)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
long long x,y,n,i,inf=1e9,j;
double vx=1e10,vy=1e10;
struct pct{double x,y,p,d; long long cad;};
pct a[120010];
stack<long long> s,st;
// REPARARE: Sortare folosind produsul vectorial in loc de pante
bool cmp(pct b,pct c){
double d=b.x*c.y-b.y*c.x; // Pivotul e (0,0) dupa translatie
if(abs(d)<1e-11) return (b.x*b.x+b.y*b.y)<(c.x*c.x+c.y*c.y);
return d>0;
}
double det(long long x,long long y,long long z){
return a[x].x*(a[y].y-a[z].y)+a[x].y*(a[z].x-a[y].x)+a[y].x*a[z].y-a[z].x*a[y].y;
}
int main(){
fin>>n;
for(i=1;i<=n;i++){
fin>>a[i].x>>a[i].y;
if(vy>a[i].y||vy==a[i].y&&vx>a[i].x) vx=a[i].x,vy=a[i].y;
}
for(i=1;i<=n;i++){
a[i].x-=vx,a[i].y-=vy;
}
// Punem pivotul pe prima pozitie pentru a nu-l sorta
for(i=1;i<=n;i++) if(a[i].x==0&&a[i].y==0){ swap(a[1],a[i]); break; }
sort(a+2,a+n+1,cmp);
s.push(1); s.push(2);
for(i=3;i<=n;i++){
x=s.top(),s.pop();
y=s.top();
while(det(y,x,i)<=0){
x=y,s.pop(),y=s.top();
}
s.push(x),s.push(i);
}
fout<<s.size()<<'\n';
while(!s.empty()) st.push(s.top()),s.pop();
while(!st.empty()) fout<<fixed<<setprecision(6)<<a[st.top()].x+vx<<' '<<a[st.top()].y+vy<<'\n',st.pop();
return 0;
}