Pagini recente » Cod sursa (job #1219061) | Cod sursa (job #2692625) | Cod sursa (job #2088382) | Cod sursa (job #967650) | Cod sursa (job #2495818)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,tp;
struct Point {
double x,y;
};
vector<Point> p;
int st[120005];
int isLeft(const Point &P,const Point &Q,const Point &R){
return ((Q.x-P.x)*(R.y-P.y)-(Q.y-P.y)*(R.x-P.x)>0);
}
int cmp(const Point &P,const Point &Q){
return isLeft(p[1],P,Q);
}
int main(){
fin>>n;
p.resize(n+1);
for(int i=1;i<=n;i++)
fin>>p[i].x>>p[i].y;
for(int i=2;i<=n;i++)
if(p[1].x>p[i].x || (p[1].x==p[i].x && p[1].y>p[i].y))
swap(p[1],p[i]);
sort(p.begin() + 2, p.end(), cmp);
st[1]=1; st[2]=2;
tp=2;
for(int i=3;i<=n;i++){
while(tp>=2 && !isLeft(p[st[tp-1]],p[st[tp]],p[i])) --tp;
st[++tp]=i;
}
fout<<tp<<'\n';
for(int i=1;i<=tp;i++)
fout<<fixed<<setprecision(6)<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';
}