Pagini recente » Cod sursa (job #1161890) | Cod sursa (job #74782) | Cod sursa (job #2787959) | Cod sursa (job #2342436) | Cod sursa (job #795172)
Cod sursa(job #795172)
#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);
}
double SqDist(point A,point B){
return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}
int main(){
int i;
fin >> N;
for (int i = 0; i < N; i++) fin >> P[i].x >> P[i].y;
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--;
if (top > 0 && Intoarcere(st[top-1], st[top], P[i]) == 0){
if (SqDist(st[top-1], st[top]) < SqDist(st[top-1], P[i]))
st[top] = P[i];
}
else st[++top] = P[i];
}
fout << top + 1 << "\n";
for (int i = 0; i <= top; i++) fout << st[i].x << " " << st[i].y << "\n";
}