Pagini recente » Cod sursa (job #2877497) | Cod sursa (job #2849241) | Cod sursa (job #577148) | Cod sursa (job #3000238) | Cod sursa (job #3196415)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out("infasuratoare.out");
#define maxN 120000
struct point{
double x,y;
}v[maxN+1];
#define maxVal 1000000000
double minx=maxVal,miny=maxVal;
vector <point>st;
bool cmp(point a,point b){
return (-minx+a.x)*(-miny+b.y)>(-miny+a.y)*(-minx+b.x);
}
double slope(point a,point b){
return a.x*b.y-a.y*b.x;
}
int orient(point a,point b,point c){
double val=slope(a,b)+slope(b,c)+slope(c,a);
if(val>0){
return 1;
}
else{
if(val==0){
return 2;
}
else{
return 3;
}
}
}
int main(){
double x,y;
int n;
in>>n;
for(int i=1;i<=n;i++){
in>>v[i].x>>v[i].y;
if(v[i].y<miny){
miny=v[i].y;
minx=v[i].x;
swap(v[1],v[i]);
}
}
sort(v+2,v+n+1,cmp);
st.push_back(v[1]);
st.push_back(v[2]);
for(int i=3;i<=n;i++){
while(st.size()>1 && orient(st[st.size()-2],st[st.size()-1],v[i])!=1){
st.pop_back();
}
st.push_back(v[i]);
}
out<<st.size()<<'\n';
for(int i=0;i<st.size();i++){
out<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<'\n';
}
}