Pagini recente » Cod sursa (job #2134724) | Cod sursa (job #2563464) | Cod sursa (job #2796313) | Cod sursa (job #1755671) | Cod sursa (job #1516038)
#include <fstream>
#include <bitset>
#include <iomanip>
#include <algorithm>
using namespace std;
pair<double, double> PTS[120001];
double cross_product(const pair<double, double>& O, const pair<double, double>& A, const pair<double, double>& B) {
return (A.first - O.first) * (B.second - O.second) - (B.first - O.first) * (A.second - O.second);
}
const double E = 1e-12;
int s[120001], len=0;
int main(){
ifstream f("infasuratoare.in");
ofstream of("infasuratoare.out");
int N;
bitset<120001> v;
f >> N;
for (int i = 1; i <= N; ++i){
f >> PTS[i].first >> PTS[i].second;
}
sort(PTS+1, PTS + N + 1);
s[++len] = 1;
s[++len] = 2;
v[2] = 1;
for (int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p)))
if (!v[i]){
while (len >= 2 && cross_product(PTS[s[len-1]], PTS[s[len]], PTS[i]) > 0)
v[s[len--]] = 0;
s[++len] = i;
v[i] = 1;
}
of << len-1 <<"\n";
of << setprecision(6) << fixed;
for (int i = 1; i < len; ++i)
of << PTS[s[i]].first << " " << PTS[s[i]].second << "\n";
}