Pagini recente » Cod sursa (job #1154382) | Cod sursa (job #691209) | Cod sursa (job #2896571) | Cod sursa (job #1246292) | Cod sursa (job #2374924)
#include <bits/stdc++.h>
using namespace std;
#define LMAX 120005
#define x first
#define y second
typedef pair<long double,long double> point;
point p[LMAX];
int det(point a,point b,point c){
return (a.x*b.y+b.x*c.y+c.x*a.y)-(a.y*b.x+b.y*c.x+c.y*a.x);
}
bool cmp(point a,point b){
return det(p[1],a,b)>0;
}
int top=0,st[LMAX];
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>p[i].x>>p[i].y;
if(i>1&&p[i]<p[1])
swap(p[i],p[1]);
}
sort(p+2,p+n+1,cmp);
int top=0;
for(int i=1;i<=n;++i){
while(top>1&&det(p[st[top-1]],p[st[top]],p[i])<=0)
--top;
st[++top]=i;
}
cout<<top<<"\n";
for(int i=1;i<=top;++i)
cout<<fixed<<setprecision(6)<<p[st[i]].x<<" "<<p[st[i]].y<<"\n";
return 0;
}