Pagini recente » Cod sursa (job #3236417) | Cod sursa (job #739127) | Cod sursa (job #655956) | Cod sursa (job #1440408) | Cod sursa (job #795167)
Cod sursa(job #795167)
#include <fstream>
#include <algorithm>
#define inf 0xfffffff
using namespace std;
ifstream fin("infasuratoare.in"); ofstream fout("infasuratoare.out");
struct point{
double x, y;
bool operator < (point const &b) const{
return x > b.x || x == b.x && y < b.y;
}
} P[120001] , st[120001];
int N, top = -1;
double Intoarcere(point &A, point &B, point &C){
return (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y)) / 2;
}
double Sloap(point A, point B){
if (B.x == A.x) return -inf;
return (B.y - A.y)/(B.x - A.x);
}
double Cmp (point A, point B){
return Sloap(P[0], A) < Sloap(P[0], B);
}
void convex(){
int i;
sort(P, P + N);
sort(P + 1, P + N, Cmp);
for (i = 0; i < N; i++){
while (top > 1 && Intoarcere(st[top-1], st[top], P[i]) <= 0) top--;
st[++top] = P[i];
}
}
int main(){
fin >> N;
for (int i = 0; i < N; i++) fin >> P[i].x >> P[i].y;
convex();
fout << top + 1 << "\n";
for (int i = 0; i <= top; i++) fout << st[i].x << " " << st[i].y << "\n";
}