Pagini recente » Cod sursa (job #1775547) | Cod sursa (job #1806103) | Cod sursa (job #1019754) | Cod sursa (job #1890047) | Cod sursa (job #1614924)
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <utility>
#include <iomanip>
#include <fstream>
using namespace std;
struct punct{
double x, y;
punct(){}
punct(const double X, const double Y): x(X), y(Y){}
};
bool operator<(const punct& a, const punct& b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool is_left_turn(punct a, const punct& b, punct c){
a.x -= b.x, c.x -= b.x;
a.y -= b.y, c.y -= b.y;
return a.x * c.y < a.y * c.x;
}
void construct_hull(const punct& rad, const vector<punct>& pts, deque<punct>& rez){
rez.push_front(rad);
rez.push_front(pts[0]);
for(int i = 1; i < pts.size(); ++i){
while(rez.size() > 1 && !is_left_turn(rez[1], rez[0], pts[i])){
rez.pop_front();
}
rez.push_front(pts[i]);
}
reverse(rez.begin(), rez.end());
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
f >> n;
vector<punct> v(n);
for(int i = 0; i < v.size(); ++i){
f >> v[i].x >> v[i].y; }
sort(v.begin(), v.end());
vector<punct> over, under;
for(int i = 1; i < n-1; ++i){
(is_left_turn(v[0], v[i], v[n-1]) ? under : over)
.push_back(v[i]); }
reverse(over.begin(), over.end());
deque<punct> hull_over, hull_under;
construct_hull(v[n-1], over, hull_over);
construct_hull(v[0], under, hull_under);
vector<punct> hull(hull_under.begin(), hull_under.end());
hull.insert(hull.end(), hull_over.begin(), hull_over.end());
g << hull.size() << '\n';
g << fixed << setprecision(6);
for(int i = 0; i < hull.size(); ++i){
g << hull[i].x << ' ' << hull[i].y << '\n';
}
return 0;
}