Pagini recente » Cod sursa (job #782067) | Cod sursa (job #269388) | Cod sursa (job #955325) | Cod sursa (job #1405276) | Cod sursa (job #2171923)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define prec 0.0000000000001
using namespace std;
typedef pair<long double, long double> Point;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector<Point> puncte;
vector<Point> infasuratoare, infasuratoare2;
int N, i;
long 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(fabs(currentP.first - infasuratoare[infasuratoare.size() - 1].first) < prec)
{
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(fabs(currentP.first - infasuratoare2[infasuratoare2.size() - 1].first) < prec)
{
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<<fixed<<setprecision(6)<<infasuratoare[i].second<<" "<<infasuratoare[i].first<<'\n';
}
for(i = 1; i < infasuratoare.size() - 1; ++i)
{
fout<<fixed<<setprecision(6)<<infasuratoare2[i].second<<" "<<infasuratoare2[i].first<<'\n';
}
fout.close();
return 0;
}