Pagini recente » Cod sursa (job #58019) | Cod sursa (job #2569588) | Cod sursa (job #1981801) | Cod sursa (job #3124359) | Cod sursa (job #2836884)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120005;
int N;
struct point{
float x, y;
};
point points[NMAX], p0;
int orientation(point p, point q, point r){
float 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
}
float 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 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(10);
while(!st.empty()){
fout<<st.top().x<<' '<<st.top().y<<'\n';
st.pop();
}
}
int main()
{
fin>>N;
float x, y;
for(int i=1;i<=N;i++){
fin>>x>>y;
points[i]={x,y};
}
convexHull();
fin.close();
fout.close();
return 0;
}