Pagini recente » Cod sursa (job #616628) | Cod sursa (job #1173818) | Cod sursa (job #2756792) | Profil SpiriFlaviu | Cod sursa (job #2171825)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define prec 0.000000000001
using namespace std;
typedef pair<double, double> Point;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector<Point> puncte;
vector<Point> infasuratoare, infasuratoare2;
int N, i;
double auxX, auxY, t1, t2;
Point currentP;
bool sortY(Point a, Point b)
{
return (a.first < b.first);
}
int main()
{
fin>>N;
for(i = 0; i < N; ++i)
{
fin>>auxX>>auxY;
puncte.push_back(make_pair(auxY, auxX));
}
sort(puncte.begin(), puncte.end(), sortY);
infasuratoare.push_back(puncte[0]);
infasuratoare.push_back(puncte[1]);
for(i = 2; i < N; ++i)
{
currentP = puncte[i];
if(currentP.first == infasuratoare[infasuratoare.size() - 1].first)
{
if(currentP.second > infasuratoare[infasuratoare.size() - 1].second)
{
infasuratoare.pop_back();
t1 = (currentP.second - infasuratoare[infasuratoare.size() - 2].second) / (currentP.first - infasuratoare[infasuratoare.size() - 2].first);
t2 = (currentP.second - infasuratoare[infasuratoare.size() - 1].second) / (currentP.first - infasuratoare[infasuratoare.size() - 1].first);
while(t1 < t2 && infasuratoare.size() > 1)
{
infasuratoare.pop_back();
t1 = (currentP.second - infasuratoare[infasuratoare.size() - 2].second) / (currentP.first - infasuratoare[infasuratoare.size() - 2].first);
t2 = (currentP.second - infasuratoare[infasuratoare.size() - 1].second) / (currentP.first - infasuratoare[infasuratoare.size() - 1].first);
}
infasuratoare.push_back(currentP);
}
}
else
{
t1 = (currentP.second - infasuratoare[infasuratoare.size() - 2].second) / (currentP.first - infasuratoare[infasuratoare.size() - 2].first);
t2 = (currentP.second - infasuratoare[infasuratoare.size() - 1].second) / (currentP.first - infasuratoare[infasuratoare.size() - 1].first);
while(t1 < t2 && infasuratoare.size() > 1)
{
infasuratoare.pop_back();
t1 = (currentP.second - infasuratoare[infasuratoare.size() - 2].second) / (currentP.first - infasuratoare[infasuratoare.size() - 2].first);
t2 = (currentP.second - infasuratoare[infasuratoare.size() - 1].second) / (currentP.first - infasuratoare[infasuratoare.size() - 1].first);
}
infasuratoare.push_back(currentP);
}
}
infasuratoare2.push_back(puncte[N - 1]);
infasuratoare2.push_back(puncte[N - 2]);
for(i = N - 3; i > -1; --i)
{
currentP = puncte[i];
if(currentP.first == infasuratoare2[infasuratoare2.size() - 1].first)
{
if(currentP.second < infasuratoare2[infasuratoare2.size() - 1].second)
{
infasuratoare2.pop_back();
t1 = (currentP.second - infasuratoare2[infasuratoare2.size() - 2].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 2].first);
t2 = (currentP.second - infasuratoare2[infasuratoare2.size() - 1].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 1].first);
while(t1 < t2 && infasuratoare2.size() > 1)
{
infasuratoare2.pop_back();
t1 = (currentP.second - infasuratoare2[infasuratoare2.size() - 2].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 2].first);
t2 = (currentP.second - infasuratoare2[infasuratoare2.size() - 1].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 1].first);
}
infasuratoare2.push_back(currentP);
}
}
else
{
t1 = (currentP.second - infasuratoare2[infasuratoare2.size() - 2].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 2].first);
t2 = (currentP.second - infasuratoare2[infasuratoare2.size() - 1].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 1].first);
while(t1 < t2 && infasuratoare2.size() > 1)
{
infasuratoare2.pop_back();
t1 = (currentP.second - infasuratoare2[infasuratoare2.size() - 2].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 2].first);
t2 = (currentP.second - infasuratoare2[infasuratoare2.size() - 1].second) / (currentP.first - infasuratoare2[infasuratoare2.size() - 1].first);
}
infasuratoare2.push_back(currentP);
}
}
fout<<infasuratoare.size() + infasuratoare2.size() - 2<<'\n';
for(i = 0; i < infasuratoare.size(); ++i)
{
fout<<infasuratoare[i].second<<" "<<infasuratoare[i].first<<'\n';
}
for(i = 1; i < infasuratoare.size() - 1; ++i)
{
fout<<infasuratoare2[i].second<<" "<<infasuratoare2[i].first<<'\n';
}
return 0;
}