Pagini recente » Rating Radical (skrillex) | Cod sursa (job #893622) | Cod sursa (job #1849285) | Cod sursa (job #2024501) | Cod sursa (job #2836893)
#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, st[NMAX];
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;
}
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);
int vf=0;
st[++vf]=points[1];
st[++vf]=points[2];
for(int i=3;i<=N;i++){
while(vf>1 and orientation(st[vf-1],st[vf],points[i])!=2)
vf--;
st[++vf]=points[i];
}
fout<<vf<<'\n';
fout<<fixed<<setprecision(12);
for(int i=1;i<=vf;i++)
fout<<st[i].x<<' '<<st[i].y<<'\n';
}
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;
}