Pagini recente » Cod sursa (job #885737) | Autentificare | Cod sursa (job #2219145) | Cod sursa (job #168096) | Cod sursa (job #3268064)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAX=12e4;
int n,i;
stack <int> s;
struct elem{
double x,y;}v[MAX+5];
double abs(double x)
{
if (x<=0)
return -x;
return x;
}
double determinant(double x1, double y1, double x2, double y2, double x3, double y3)
{
return x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
}
bool compare(elem a, elem b)
{
if (a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
bool unghi(elem a, elem b, elem c)
{
return determinant(a.x,a.y,b.x,b.y,c.x,c.y)<0;
}
bool compare2(elem a, elem b)
{
return unghi(v[1],a,b);
}
int main()
{
fin>>n;
for (i=1; i<=n; i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,compare);
s.push(1);
sort(v+2,v+n+1,compare2);
s.push(2);
for (i=3; i<=n; i++)
{
while (s.size()>=2)
{
int ind1=s.top();
s.pop();
int ind2=s.top();
double x1=v[ind2].x, y1=v[ind2].y, x2=v[ind1].x, y2=v[ind1].y, x3=v[i].x, y3=v[i].y;
if (determinant(x1,y1,x2,y2,x3,y3)<=0)
{
s.push(ind1);
break;
}
}
s.push(i);
}
fout<<s.size()<<"\n";
while (!s.empty())
{
fout<<fixed<<setprecision(6)<<v[s.top()].x<<" "<<v[s.top()].y<<"\n";
s.pop();
}
return 0;
}