Pagini recente » Cod sursa (job #685129) | Cod sursa (job #2497137) | Cod sursa (job #891544) | Cod sursa (job #712141) | Cod sursa (job #1951363)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define maxN 120001
#define xMax 1000000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, aux;
struct punct {
float x, y;
} v[maxN];
int st[maxN];
bool prod(punct O, punct A, punct B) {
float p1 = (A.y - O.y)*(B.x - O.x);
float p2 = (B.y - O.y)*(A.x - O.x);
return p1 < p2;
}
bool comp(punct A, punct B) {
return prod(v[1], A, B);
}
int main()
{
fin>>n;
punct P;
P.x = xMax;
P.y = xMax;
for(int i = 1; i <= n; i++) {
fin>>v[i].x>>v[i].y;
if(v[i].x < P.x) {
P.x = v[i].x;
P.y = v[i].y;
aux = i;
} else if (v[i].x == P.x) {
if(v[i].y < P.y) {
P.y = v[i].y;
aux = i;
}
}
}
P = v[aux];
v[aux] = v[1];
v[1] = P;
sort(v + 2, v + n + 1, comp);
int k = 2;
st[1] = 1;
st[2] = 2;
for(int i = 3; i <= n; i++) {
while(!prod(v[st[k - 1]], v[st[k]], v[i]) && k >= 2) {
k--;
}
k++;
st[k] = i;
}
fout<<k<<'\n';
for(int i = 1; i <= k; i++) {
fout<<setprecision(9)<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
}
fin.close();
fout.close();
return 0;
}