Pagini recente » Cod sursa (job #490731) | Cod sursa (job #956352) | Cod sursa (job #125375) | Cod sursa (job #2258503) | Cod sursa (job #1217397)
#include <iostream>
#include <fstream>
#include <map>
#include <string.h>
#include <string>
#include <vector>
#include <set>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct pp
{
double x,y;
};
vector<pp> v;
int m = 1;
bool ccw(pp a, pp b, pp c)
{
if ( (b.x-a.x)*(c.y-a.y) - (b.y - a.y)*(c.x - a.x) >= 0) return true;
else return false;
}
bool comp(pp b, pp c)
{
return ( atan2(b.y-v[0].y,b.x - v[0].x)<atan2(c.y-v[0].y,c.x - v[0].x) );
}
int main()
{
fin>>n;
{
pp t;
t.x=0;
t.y = 0;
v.push_back(t);
}
for (int i=0; i<n; i++)
{
pp x;
fin>>x.x>>x.y;
v.push_back(x);
}
for (int i=1; i<n; i++)
if (v[i].y<=v[m].y)
{
if (v[i].y == v[m].y && v[i].x<v[m].x) m=i;
else if (v[i].y != v[m].y) m=i;
}
swap(v[m],v[1]);
v[0] = v[1];
sort(v.begin()+2,v.end(),comp);
int a=1;
for (int i=2; i<=n; i++)
{
while(!ccw(v[a-1],v[a],v[i]))
if (a>1) a--;
else if (i==n) break;
else i++;
a++;
swap(v[i],v[a]);
}
fout<<a<<'\n';
for (int i=1; i<=a; i++)
fout<<setprecision(9)<<fixed<<v[i].x<<' '<<v[i].y<<'\n';
return 0;
}