Pagini recente » Cod sursa (job #2715610) | Cod sursa (job #1795473) | Cod sursa (job #2299260) | Cod sursa (job #2653508) | Cod sursa (job #2551525)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <queue>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct point {
double x, y;
} puncte[120004];
queue<point> Q;
bool compare(point x, point y) {
return x.x < y.x;
}
void citire() {
f >> n;
for (int i = 0; i < n; ++i) {
f >> puncte[i].x >> puncte[i].y;
}
}
void afis(point a) {
g << setprecision(13) << fixed << a.x << " " << a.y << endl;
}
bool sens_trigo(point A, point B, point C) {
double det = (A.x - C.x) * (B.y - C.y) - (A.y - C.y) * (B.x - C.x);
return det >= 0;
}
void rezolvare() {
point A, B;
int nr=0;
A = puncte[0], B = puncte[1];
//Q.push(A);
for (int i = 2; i < n; i++) {
if (!sens_trigo(A, B, puncte[i])) {
B = puncte[i];
} else {
Q.push(B);
nr++;
A = B;
B = puncte[i];
}
}
if (sens_trigo(A, B, puncte[n-1])) {
Q.push(B);
nr++;
A = B;
B = puncte[n-1];
}
A=puncte[n-1], B=puncte[n-2];
for (int i = n-3; i >=0; i--) {
if (!sens_trigo(A, B, puncte[i])) {
B = puncte[i];
} else {
Q.push(B);
nr++;
A = B;
B = puncte[i];
}
}
if (sens_trigo(A, B, puncte[0])) {
Q.push(B);
nr++;
A = B;
B = puncte[0];
}
g<<nr<<endl;
while(!Q.empty()){
afis(Q.front());
Q.pop();
}
}
int main() {
citire();
sort(puncte, puncte + n, compare);
rezolvare();
return 0;
}