Pagini recente » Cod sursa (job #1012218) | Cod sursa (job #2473836) | Cod sursa (job #1898534) | Cod sursa (job #1889176) | Cod sursa (job #2836889)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120005;
int N;
struct point{
double x, y;
};
point points[NMAX], p0;
int orientation(point p, point q, point r){
double val=(q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y);
if(val==0) return 0; ///collinear
if(val>0) return 1; ///clockwise
return 2; ///counterclockwise
}
double dist(point p, point q){
return (q.x-p.x)*(q.x-p.x)+(q.y-p.y)*(q.y-p.y);
}
bool comp(point A, point B){
int o=orientation(p0,A,B);
if(o==0)
return dist(p0,A)<dist(p0,B);
if(o==1) return 0;
return 1;
}
point nexToTop(stack<point> st){
point p=st.top();
st.pop();
point res=st.top();
st.push(p);
return res;
}
void afisare(stack<point> st){
if(!st.empty()){
point res=st.top();
st.pop();
afisare(st);
fout<<res.x<<' '<<res.y<<'\n';
}
}
void convexHull()
{
int mn=1;
for(int i=2;i<=N;i++){
if(points[i].y<points[mn].y)
mn=i;
else if(points[i].y==points[mn].y and points[i].x<points[mn].x)
mn=i;
}
p0=points[mn];
swap(points[1],points[mn]);
sort(points+2,points+N+1,comp);
stack<point> st;
st.push({points[1]});
st.push({points[2]});
st.push({points[3]});
for(int i=4;i<=N;i++){
while(st.size()>=3 and orientation(nexToTop(st),st.top(),points[i])!=2)
st.pop();
st.push(points[i]);
}
fout<<st.size()<<'\n';
fout<<fixed<<setprecision(12);
afisare(st);
}
int main()
{
fin>>N;
double x, y;
for(int i=1;i<=N;i++){
fin>>x>>y;
points[i]={x,y};
}
convexHull();
fin.close();
fout.close();
return 0;
}