Pagini recente » Cod sursa (job #1781868) | Cod sursa (job #1034270) | Diferente pentru runda/oji20-20_dau_leak_la_probleme_smr intre reviziile 2 si 3 | Cod sursa (job #1754705) | Cod sursa (job #1073231)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
#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];
punct make_punct(int x, int y, int i) {
return make_pair(make_pair (x, y), i);
}
inline int cross (punct A, punct B, punct C) {
return (B.X - A.X) * (C.Y - A.Y) - (C.X - A.X) * (B.Y - A.Y);
}
bool cmp(punct A, punct B) {
return cross (P[0], A, B) < 0;
}
bool coord_cmp (punct A, punct B) {
return A.first > B.first;
}
int main() {
fin >> n;
for (int i = 0; i < n; ++i) {
double x, y;
fin >> x >> y;
P.push_back (make_punct(x, y, i));
if (P[MIN] > P[i])
MIN = i;
}
swap (P[0], P[MIN]);
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]);
}
fout << S.size() << "\n" << fixed << setprecision(9);
for (vector <punct> :: reverse_iterator it = S.rbegin(); it != S.rend(); ++it)
fout << it->X << " " << it->Y << "\n";
/*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;
fout << 0 << " ";
for (int i = Start; i != Start-1; i = (i + 1) % n)
fout << sol[i].NO << " ";*/
}