Pagini recente » Cod sursa (job #527125) | Cod sursa (job #774521) | Cod sursa (job #3136462) | Cod sursa (job #2163803) | Cod sursa (job #3195704)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define N_MAX 150005
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;
}
double 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]);
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(){
FILE *in, *out;
in = fopen ("infasuratoare.in", "r");
out = fopen ("infasuratoare.out", "w");
int n;
fscanf (in, "%d", &n);
for (int i=0; i<n; ++i)
fscanf (in, "%lf%lf", &points[i].x, &points[i].y);
swap (points[0], points[startingPoint(n)]);
sort (points + 1, points + n, cmp);
findAns (n);
fprintf (out, "%d \n", ans.size());
for (point p:ans){
fprintf (out, "%.12lf %.12lf \n", p.x, p.y);
}
return 0;
}