Pagini recente » Cod sursa (job #1835801) | Cod sursa (job #2502663) | Cod sursa (job #277139) | Cod sursa (job #2623692) | Cod sursa (job #2360289)
#include <bits/stdc++.h>
#define Nmax 120005
#define ld long double
#define _point pair <ld,ld>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
_point P[Nmax];
_point st[Nmax];
int N,k;
inline bool det(const _point &p1, const _point &p2, const _point &p3){
return p1.x*p2.y-p1.y*p2.x+p2.x*p3.y-p2.y*p3.x+p3.x*p1.y-p3.y*p1.x<=0;
}
inline bool comp(const _point &lsh, const _point &rsh){
return (lsh.y-P[1].y)*(rsh.x-P[1].x)<(lsh.x-P[1].x)*(rsh.y-P[1].y);
}
void read_data(){
f>>N;
int pos=1;
for(int i=1;i<=N;i++){
f>>P[i].x>>P[i].y;
if(P[i]<P[pos])
pos=i;
}
swap(P[1],P[pos]);
}
void solve(){
sort(P+2,P+N+1,comp);
st[++k]=P[1];
st[++k]=P[2];
for(int i=3;i<=N;i++){
while(k>1 and det(st[k-1],st[k],P[i]))
--k;
st[++k]=P[i];
}
}
void print_ans(){
g<<k<<fixed<<setprecision(6)<<'\n';
for(int i=1;i<=k;i++)
g<<st[i].x<<' '<<st[i].y<<'\n';
}
int main(){
read_data();
solve();
print_ans();
return 0;
}