Pagini recente » Cod sursa (job #2217550) | Cod sursa (job #265562) | Cod sursa (job #2180230) | hc_bonus_round | Cod sursa (job #1411084)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector<pair<double,double> > v,q;
vector<pair<double,double> >::iterator it;
pair<double,double> A,B;
int n,i;
double xMin,yMin,x,y;
bool cmp(pair<double,double> a, pair<double,double> b)
{
if ((a.first-xMin)/(a.second-yMin)>(b.first-xMin)/(b.second-yMin))
return true;
else
return false;
}
int main()
{
fin>>n;
fin>>xMin>>yMin;
for (i=1;i<n;i++)
{
fin>>x>>y;
if (y<yMin)
{
swap(y,yMin);
swap(x,xMin);
}
else if (y==yMin)
{
if (x<xMin)
{
swap(y,yMin);
swap(x,xMin);
}
}
v.push_back(make_pair(x,y));
}
sort(v.begin(),v.end(),cmp);
q.push_back(make_pair(xMin,yMin));
it = v.begin();
A = q.front();
q.push_back(*it);
v.erase(v.begin());
for (vector<pair<double,double> >::iterator it = v.begin(); it != v.end(); it ++)
{
B = q.back();
if ( (B.first-A.first)*((*it).second-A.second)-(B.second-A.second)*((*it).first-A.first) > 0) // ok
{
A=B;
q.push_back(*it);
}
else //nu ok
{
q.pop_back();
q.push_back(*it);
}
}
fout<<q.size()<<"\n";
for (vector<pair<double,double> >::iterator it = q.begin(); it != q.end(); it++)
fout<<(*it).first<<" "<<(*it).second<<"\n";
return 0;
}