Pagini recente » Cod sursa (job #2785548) | Cod sursa (job #2698808) | Cod sursa (job #2953185) | Cod sursa (job #2853377) | Cod sursa (job #2984715)
#include<iostream>
#include<deque>
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
struct point{
double x,y;
};
bool compare1(const point&a, const point&b){
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
bool compare2(const point&a, const point&b){
return a.x>b.x || (a.x==b.x && a.y>b.y);
}
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
vector<point> points;
void read(){
in>>n;
points.resize(n);
for(int i=0;i<n;i++){
in>>points[i].x>>points[i].y;
}
}
/* 1 1 1
* a.x b.x c.x
* a.y b.y c.y
*/
double determinant(point a, point b, point c){
return (b.x*c.y) + (a.x*b.y) + (a.y*c.x) - (b.x*a.y) - (c.x*b.y) - (c.y*a.x);
}
vector<point> get_hull(){
vector<point> hull;
hull.push_back(points[0]);
hull.push_back(points[1]);
for(int i=2;i<n;i++){
while(hull.size()>=2 && determinant(hull[hull.size()-2],hull[hull.size()-1],points[i])<=0 ){
hull.pop_back();
}
hull.push_back(points[i]);
}
return hull;
}
void solve(){
sort(points.begin(),points.end(),compare1);
vector<point> lower = get_hull();
sort(points.begin(),points.end(),compare2);
vector<point> upper = get_hull();
lower.pop_back();
upper.pop_back();
out<<lower.size()+upper.size()<<'\n';
for(point a:lower){
out<<fixed<<setprecision(10)<<a.x<<" "<<a.y<<'\n';
}
for(point a:upper){
out<<fixed<<setprecision(10)<<a.x<<" "<<a.y<<'\n';
}
}
int main(){
read();
solve();
return 0;
}