Pagini recente » Cod sursa (job #2893392) | Cod sursa (job #2357441) | Cod sursa (job #2505439) | Cod sursa (job #2893064) | Cod sursa (job #1882518)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMax = 120003;
const int INF = 0x3f3f3f3f;
struct stat{
double x,y;
};
stat a[NMax];
double mnx;
int s[NMax];
int n,mnxind,top;
double unghi(stat A, stat B, stat C){
return (A.y - B.y) * (A.x - C.x) - (A.y - C.y) * (A.x - B.x);
}
bool cmp(stat x, stat y){
return (unghi(a[1],x,y) > 0);
}
int main()
{
f >> n;
double mnx = INF;
for(int i = 1; i <= n; ++i){
f >> a[i].x >> a[i].y;
if(a[i].x < mnx){
mnx = a[i].x;
mnxind = i;
}
}
swap(a[mnxind],a[1]);
sort(a + 2, a + n + 1, cmp);
s[++top] = 1;
s[++top] = 2;
for(int i = 3; i <= n; ++i){
while(unghi(a[s[top - 1]], a[s[top]], a[i]) < 0){
top--;
}
s[++top] = i;
}
g << top << '\n';
for(int i = top; i >= 1; --i){
g << fixed << setprecision(6) << a[s[i]].x << ' ' << a[s[i]].y << '\n';
}
return 0;
}