Pagini recente » Cod sursa (job #1459400) | Cod sursa (job #479359) | Cod sursa (job #2838200) | Cod sursa (job #2182434) | Cod sursa (job #1804086)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
const int INF = (-1 + (1 << 31));
struct pct {
double x, y;
} MIN;
vector< pct > V;
vector<int> S;
int N;
void Read();
void Solve();
void Write();
double tg(const pct &a);
bool cmp(const pct &a, const pct &b) { return tg(a) > tg(b); };
bool leftTurn(const pct &a, const pct &b, const pct &c);
int main()
{
Read();
Solve();
Write();
return 0;
}
void Write() {
cout << S.size() << '\n';
for(int i = S.size() - 1; i >= 0; i--)
cout << fixed << setprecision(6) << V[ S[i] ].x << ' ' << V[ S[i] ].y << '\n';
}
void Solve() {
sort(V.begin(), V.end(), cmp);
for(int i = 0; i < N; i++) {
while(S.size() > 1 && leftTurn(V[ S[S.size()-2] ], V[ S[S.size()-1] ], V[i]))
S.pop_back();
S.push_back(i);
}
}
bool leftTurn(const pct &a, const pct &b, const pct &c) {
int x1, y1, x2, y2;
x1 = b.x - a.x;
y1 = b.y - a.y;
x2 = c.x - a.x;
y2 = c.y - a.y;
return x1*y2 > y1*x2;
}
double tg(const pct &a) {
double x = a.x - MIN.x;
double y = a.y - MIN.y;
if(x == 0) {
if(y == 0)
return INF;
return INF - 1;
}
return (double)(y / x);
}
void Read() {
freopen("infasuratoare.in", "rt", stdin);
freopen("infasuratoare.out", "wt", stdout);
scanf("%d", &N);
pct aux;
V.assign(N, pct());
MIN.x = MIN.y = INF;
for(int i = 0; i < N; i++) {
scanf("%lf %lf", &aux.x, &aux.y);
V[i] = aux;
if(aux.x < MIN.x || ( aux.x == MIN.x && aux.y < MIN.y ) )
MIN = aux;
}
}