Pagini recente » Cod sursa (job #2101295) | Cod sursa (job #1594343) | Cod sursa (job #2778931) | Cod sursa (job #227485) | Cod sursa (job #1422175)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
class point{
public:
double x,y;
bool operator<(const point& a) const{
return (x < a.x || (x==a.x && y > a.y));
}
point(){x=y=0;}
point(double a, double b){
x =a;
y = b;
}
};
double cross_prod(point&a,point&b,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(std::vector<point> v){
sort(v.begin(),v.end());
int n = v.size();
vector<point>l;
vector<point>u;
for(int i = 0,k=0; i<n;i++){
if(k>=2){
double value = cross_prod(l[k-2],l[k-1],v[i]);
if(value >= 0) {
l.pop_back();
k--;
}
}
l.push_back(v[i]);
k++;
}
for(int i = v.size()-1,k=0; i>=0;i--){
if(k>=2){
double value = cross_prod(u[k-2],u[k-1],v[i]);
if(value >= 0) {
u.pop_back();
k--;
}
}
u.push_back(v[i]);
k++;
}
l.pop_back();
for(int k =0; k< u.size()-1;k++)
l.push_back(u[k]);
fout<<setprecision(6) << fixed;
for(int i =l.size()-1; i >=0; i--)
fout << l[i].x << " " << l[i].y << endl;
}
int main(){
vector<point>v;
int n;
fin >> n;
for(int i =0 ; i < n; i++){
double a,b;
fin >> a >> b;
v.push_back(point(a,b));
}
convex_hull(v);
return 0;
}