Pagini recente » Cod sursa (job #3349279) | Cod sursa (job #2544766) | Cod sursa (job #3340610) | Cod sursa (job #2857174) | Cod sursa (job #3355108)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <cmath>
using namespace std;
ifstream I("infasuratoare.in");
ofstream O("infasuratoare.out");
const int GMAN = 120005;
const double eps = 1.e-12;
struct point {
double x, y;
};
point a[GMAN];
point ll;
stack<point> st;
double cp(point P1, point P2, point P3) {
return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}
int ccw(point P1, point P2, point P3) {
double product;
product = cp(P1, P2, P3);
if (fabs(product) < eps)
return 0;
if (product > eps)
return 1;
return -1;
}
bool cmp(point a, point b) {
if (ccw(ll, a, b) == -1)
return 0;
return 1;
}
int main(){
O << fixed << showpoint << setprecision(6);
int n;
point temmie;
I >> n;
I >> temmie.x >> temmie.y;
a[1] = temmie;
for (int i = 2; i <= n; i++) {
I >> temmie.x >> temmie.y;
if (fabs(a[1].y - temmie.y) < eps) {
if (a[1].x - temmie.x >= eps) {
a[i] = a[1];
a[1] = temmie;
continue;
}
}
if (a[1].y - temmie.y >= eps) {
a[i] = a[1];
a[1] = temmie;
continue;
}
a[i] = temmie;
}
ll = a[1];
sort(a + 2, a + n + 1, cmp);
//for (int i = 1; i <= n; i++) {
// O << a[i].x << ' ' << a[i].y << '\n';
//}
//O << '\n';
st.push(ll);
st.push(a[2]);
point l = ll, ler = a[2];
a[n + 1] = ll;
for (int i = 3; i <= n+1; i++) {
point tem = a[i];
int t = ccw(l, ler, tem);
switch (t) {
case -1:
st.pop();
ler = st.top();
st.pop();
l = st.top();
st.push(ler);
i--;
break;
case 1:
st.push(tem);
l = ler;
ler = tem;
break;
}
}
st.pop();
O << st.size() << '\n';
stack<point> temst;
while (!st.empty()) {
temst.push(st.top());
st.pop();
}
while (!temst.empty()) {
O << temst.top().x << ' ' << temst.top().y << '\n';
temst.pop();
}
return 0;
}