Pagini recente » Cod sursa (job #1740808) | Cod sursa (job #404095) | Cod sursa (job #1316258) | Cod sursa (job #2797317) | Cod sursa (job #1608312)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n;
struct Point{
double x, y;
Point(double x = 0, double y = 0): x(x), y(y) {}
bool operator()(Point A, Point B){
if (A.x != B.x)
return A.x < B.x;
return A.y < B.y;
}
};
vector<Point> elem, v1, v2;
void readData(){
double x, y;
scanf("%d\n", &n);
for (int i = 0; i < n; ++i){
scanf("%lf %lf\n", &x, &y);
elem.push_back(Point(x, y));
}
}
double det(Point A, Point B, Point C){
return A.x*B.y + B.x*C.y + C.x*A.y - B.y*C.x - A.y*B.x - A.x*C.y;
}
void insertElement(vector<Point> &v, Point p){
while (v.size() >= 2 && det(v[v.size()-2], v[v.size()-1], p)<=0)
v.pop_back();
v.push_back(p);
}
void solve(){
sort(elem.begin(), elem.end(), Point());
for (int i = 0; i < elem.size(); ++i)
insertElement(v1, elem[i]);
v2.push_back(v1[v1.size()-1]);
for (int i = elem.size()-1; i >= 0; --i)
insertElement(v2, elem[i]);
v1.pop_back(); v2.pop_back();
for (int i = 0; i < v2.size(); ++i)
v1.push_back(v2[i]);
printf("%d\n", v1.size());
for (int i = 0; i < v1.size(); ++i)
printf("%lf %lf\n", v1[i].x, v1[i].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
readData();
solve();
return 0;
}