Pagini recente » Istoria paginii utilizator/barosan4422 | Cod sursa (job #901869) | Cod sursa (job #772885) | Cod sursa (job #1979637) | Cod sursa (job #1073261)
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
#define X first.first
#define Y first.second
#define NO second
const int N = 1e3+5;
typedef pair <pair <double, double>, int> punct;
vector <punct> P, S, sol;
int n, MIN;
bool used[N];
inline int cross (punct A, punct B, punct C) {
return (B.first.first - A.first.first) * (C.first.second - A.first.second) - (C.first.first - A.first.first) * (B.first.second - A.first.second);
}
inline bool cmp(punct A, punct B) {
return cross (P[0], A, B) < 0;
}
inline bool coord_cmp (punct A, punct B) {
return A.first > B.first;
}
void Infasuratoare() {
printf ("%d\n", S.size());
for (int i = S.size()-1; i >= 0; --i)
printf ("%.9lf %.9lf\n", S[i].first.first, S[i].first.second);
}
int main() {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
scanf ("%d\n", &n);
int pos = 0;
for (int i = 0; i < n; ++i) {
punct p;
scanf ("%lf %lf", &p.first.first, &p.first.second);
p.second = i;
P.push_back(p);
if (P[pos] > P[i])
pos = i;
}
swap (P[pos], P[0]);
sort(P.begin()+1, P.end(), cmp);
S.push_back (P[0]);
S.push_back (P[1]);
for (int i = 2; i < n; ++i) {
while (S.size() > 1 && cross (S[S.size()-2], S[S.size()-1], P[i]) >= 0)
S.pop_back();
S.push_back (P[i]);
}
Infasuratoare();
/*
int s = 0;
for (vector <punct> :: iterator it = S.begin(); it->X <= (it+1)->X && it != S.end(); ++it) {
sol.push_back(*it);
used[it->NO] = 1;
s++;
}
sol.push_back (S[s]);
used[sol[s++].NO] = 1;
for (vector <punct> :: iterator it = P.begin(); it != P.end(); ++it)
if (!used[it->NO])
sol.push_back (*it);
sort (sol.begin()+s, sol.end(), coord_cmp);
int Start = 0;
for (int i = 0; i < n; ++i)
if(!sol[i].NO)
Start = (i + 1) % n;
printf ("0 ");
for (int i = Start; i != Start-1; i = (i + 1) % n)
printf ("%d ", sol[i].NO);*/
}