Pagini recente » Cod sursa (job #2207511) | Cod sursa (job #3233733) | Cod sursa (job #1240450) | Cod sursa (job #1084728) | Cod sursa (job #1422666)
#include <iostream>
#include <iomanip>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x,y;
point(double a, double b){
x = a;
y = b;
}
point(){x=0,y=0;}
bool operator<(const point &a) const{
return(x < a.x || (x==a.x && y < a.y));
}
};
double cross(const point& a, const point& b, const point &c){
return (b.x*c.y)+(a.x*b.y)+(c.x*a.y) - (b.x*a.y) - (b.y*c.x)-(a.x*c.y);
}
void convex_hull(vector<point>& v){
sort(v.begin(),v.end());
int n = v.size();
vector<point>l(2*n);
int k =0;
for(int i = 0; i < v.size(); i++){
while(k>=2 && cross(l[k-2],l[k-1],v[i]) <=0)
k--;
l[k++] = v[i];
}
int l_size =k;
vector<point>u(2*n);
k = 0;
for(int i = v.size()-1; i>=0; i--){
while(k>=2 && cross(u[k-2],u[k-1],v[i]) <=0)
k--;
u[k++] = v[i];
}
int u_size = k;
fout<<setprecision(6)<<fixed;
fout << l_size + u_size-2 << endl;
for(int i = 0; i < l_size; i++){
fout << l[i].x << " " << l[i].y << endl;
}
for(int i = 1; i < u_size-1; i++){
fout << u[i].x << " " << u[i].y << endl;
}
}
int main(){
int N;
fin >> N;
vector<point> v;
for(int i =0 ; i < N; i++){
double x,y;
fin >> x >> y;
v.push_back(point(x,y));
}
convex_hull(v);
}