Pagini recente » Cod sursa (job #2737586) | Cod sursa (job #86009) | Cod sursa (job #1322036) | Cod sursa (job #2871390) | Cod sursa (job #1248640)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
class Punct;
double prodVectorial(const Punct&, const Punct&, const Punct&);
vector<Punct> v, stck;
class Punct{
public:
double x, y;
Punct(double x, double y):x(x), y(y){};
friend bool operator<(const Punct& a, const Punct& b){
return prodVectorial(v[0], a, b) > 0;
}
};
double prodVectorial(const Punct &a, const Punct &b, const Punct &c){
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
// return a.x * b.y + b.x * c.y + c.x * a.y -
// b.y * c.x + c.y * a.x + a.y * b.x;
}
void infasuratoare(){
stck.push_back(v[0]);
stck.push_back(v[1]);
for(int i = 2; i < v.size(); ++i){
while(stck.size() > 1 && prodVectorial(stck[stck.size() - 2], stck.back(), v[i]) < 0)
stck.pop_back();
stck.push_back(v[i]);
}
}
int main()
{
int n;
double x, y;
f>>n;
while(n--){
f>>x>>y;
Punct p(x, y);
v.push_back(p);
}
int mnx = v[0].x, mny = v[0].y;
for(int i = 1; i < v.size(); ++i){
if(v[i].x < mnx)
mnx = v[i].x, mny = v[i].y, swap(v[0], v[i]);
else
if(v[i].x == mnx && v[i].y < mny)
mnx = v[i].x, mny = v[i].y, swap(v[0], v[i]);
}
sort(v.begin()+1, v.end());
infasuratoare();
//
// for(int i = 0; i < v.size(); ++i)
// cout<<setprecision(9)<<v[i].x<<' '<<v[i].y<<'\n';
for(int i = 0; i < stck.size(); ++i)
g<<setprecision(9)<<stck[i].x<<' '<<stck[i].y<<'\n';
return 0;
}