Pagini recente » Cod sursa (job #1374349) | Cod sursa (job #5563) | Cod sursa (job #2155080) | Cod sursa (job #2746291) | Cod sursa (job #3196175)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nMax 150005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point {double x, y;};
point points[nMax];
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(){
int n;
fin>>n;
for (int i=0; i<n; ++i)
fin>>points[i].x>>points[i].y;
swap(points[0], points[startingPoint(n)]);
sort(points + 1, points + n, cmp);
findAns(n);
fout<<ans.size()<<"\n";
for (point p:ans){
fout<<p.x<<" "<<p.y<<"\n";
}
return 0;
}