Pagini recente » Cod sursa (job #1625104) | Cod sursa (job #1175733) | Cod sursa (job #1627919) | Cod sursa (job #2835861) | Cod sursa (job #2382779)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define NMax 120010
const int inf = (1 << 30);
struct Punct{
double x, y;
double tg;
};
int n;
Punct P[NMax];
int s[NMax], vf = -1;
struct CMP{
bool operator()(Punct & a, Punct & b){
return a.tg < b.tg;
}
};
bool arie(Punct &, Punct &, Punct &);
int main(){
int i, j;
double x, y;
int pf = 0;
fin >> n;
for(i = 0; i < n; i++){
fin >> P[i].x >> P[i].y;
if(P[i].x < P[pf].x || (P[i].x == P[pf].x && P[i].y < P[pf].y)) pf = i;
}
swap(P[0], P[pf]);
P[0].tg = 0;
P[n] = P[0];
for(i = 1; i < n; i++){
if(P[i].x == P[0].x) P[i].tg = inf;
else P[i].tg = (P[i].y - P[0].y) / (P[i].x - P[0].x);
}
sort(P + 1, P + n, CMP());
s[++vf] = 0;
s[++vf] = 1;
for(i = 2; i <= n; i++){
while(arie(P[s[vf - 1]], P[s[vf]], P[i]) && vf > 1) vf--;
s[++vf] = i;
}
fout << vf << '\n';
for(i = 0; i < vf; i++)
fout << P[s[i]].x << ' ' << P[s[i]].y << '\n';
}
bool arie(Punct & a, Punct & b, Punct & c){
double arie;
arie = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
return (arie <= 0);
}