Pagini recente » Cod sursa (job #1255028) | Cod sursa (job #1598287) | Cod sursa (job #2121208) | Cod sursa (job #2378901) | Cod sursa (job #2556582)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct point {
double x, y;
} puncte[120004];
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<< a.x << " " << a.y << '\n';
}
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() {
vector<point> rez1, rez2;
int nr1 = 2, nr2 = 2;
rez1.push_back(puncte[0]);
rez1.push_back(puncte[1]);
for (int i = 2; i < n; i++) {
while (nr1 > 1 && !sens_trigo(rez1[nr1 - 2], rez1[nr1 - 1], puncte[i])) {
nr1--;
rez1.pop_back();
}
rez1.push_back(puncte[i]);
nr1++;
}
rez2.push_back(puncte[n - 1]);
rez2.push_back(puncte[n - 2]);
for (int i = n - 3; i >= 0; i--) {
while (nr2 > 1 && !sens_trigo(rez2[nr2 - 2], rez2[nr2 - 1], puncte[i])) {
nr2--;
rez2.pop_back();
}
rez2.push_back(puncte[i]);
nr2++;
}
rez1.pop_back();
rez2.pop_back();
g << nr1 + nr2 - 2 << endl;
g<<setprecision(13)<<fixed;
for (int i = 0; i < nr1 - 1; i++) {
afis(rez1[i]);
}
for (int i = 0; i < nr2 - 1; i++) {
afis(rez2[i]);
}
// rez1.push_back(puncte[0]);
// rez1.push_back(puncte[1]);
//
// for(int i=2;i<n;i++)
// {
//
// while( nr1>1 && sens_trigo(rez1[nr1-2], rez1[nr1-1], puncte[i])==0 )
// {
// nr1--;
// rez1.pop_back();
// }
//
// rez1.push_back(puncte[i]);
// nr1++;
// }
//
// rez2.push_back(puncte[n-1]);
// rez2.push_back(puncte[n-2]);
//
// for(int i=n-3;i>=0;i--)
// {
// while(nr2 >1 && sens_trigo(rez2[nr2-2], rez2[nr2-1], puncte[i])==0)
// {
// nr2--;
// rez2.pop_back();
// }
//
// rez2.push_back(puncte[i]);
// nr2++;
// }
//
// rez1.pop_back();
// rez2.pop_back();
//
// int s=nr1+nr2-2;
//
// g<<s<<"\n";
// g<<setprecision(6)<<fixed;
//
// for(int i=0;i<nr1-1;i++)
// {
// afis(rez1[i]);
// }
// for(int i=0;i<nr2-1;i++)
// {
// afis(rez2[i]);
// }
}
int main() {
citire();
sort(puncte, puncte + n, compare);
rezolvare();
return 0;
}