Pagini recente » Cod sursa (job #2558179) | Cod sursa (job #1397216) | Monitorul de evaluare | Cod sursa (job #2535456) | Cod sursa (job #3348177)
#include <fstream>
#include <math.h>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int mxN = 12e4 + 1;
struct pct{
long double x, y;
};
int n, ind = 1;
pct p[mxN], pivot;
vector<pct> ans;
long double dis(pct a, pct b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
// [xa, ya, 1] [xa, ya, 1]
// [xb, yb, 1] -> [xb-xa, yb-ya, 0]
// [xc, yc, 1] [xc-xa, yc-ya, 0]
long double det(pct a, pct b, pct c){
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp(pct a, pct b){
long double unghi = det(pivot, a, b);
if(unghi != 0) return unghi > 0;
return dis(pivot, a) < dis(pivot, b);
}
int main(){
int min = 0;
fin >> n;
for(int i = 1; i <= n; i++){
fin >> p[i].x >> p[i].y;
if(min == 0 || p[i].y < p[min].y || (p[min].y == p[i].y && p[i].x < p[min].x))
min = i;
}
swap(p[1], p[min]);
pivot = p[1];
sort(p + 2, p + 1 + n, cmp);
ans = {p[1], p[2], p[3]};
for(int i = 4; i <= n; i++){
while(ans.size() >= 2 && det(ans[ans.size() - 2], ans[ans.size() - 1], p[i]) <= 0)
ans.pop_back();
ans.push_back(p[i]);
}
for(auto x : ans){
fout << fixed << setprecision(15) << x.x << " " << x.y << "\n";
}
}