Pagini recente » Cod sursa (job #1113224) | Cod sursa (job #581993) | Cod sursa (job #42816) | Cod sursa (job #60773) | Cod sursa (job #3195689)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define N_MAX 120001
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point {double x, y;};
point points[N_MAX];
vector <point> ans;
int startingPoint (int n){
int idx = 0;
for (int i=1; i<n; ++i){
if (points[i].x < points[idx].x || (points[i].x == points[idx].x && points[i].y < points[idx].y))
idx = i;
}
return idx;
}
int orientation (point a, point b, point c){
return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}
bool cmp (point a, point b){
return orientation(points[0], a, b) < 0; // ordine trigonometrica
}
void findAns (int n){
ans.push_back (points[0]);
ans.push_back (points[1]); // tot timpul ma raportez la 3 puncte pentru sens si deaia bag la inceput primele puncte chiar daca al doilea poate nu face parte din ans
for (int i=2; i<n; ++i){
while (ans.size() >= 2 && orientation(ans[ans.size() - 2], ans.back(), points[i]) >= 0)
ans.pop_back();
ans.push_back(points[i]);
}
}
int main(){
int n;
in >> n;
for (int i=0; i<n; ++i)
in >> points[i].x >> points[i].y;
swap (points[0], points[startingPoint(n)]);
sort (points + 1, points + n, cmp);
findAns (n);
// sort (ans.begin(), ans.end(), cmp);
for (point p:ans){
out << setprecision(12) << p.x << ' ' << setprecision(12) << p.y << '\n';
}
return 0;
}