Pagini recente » Cod sursa (job #156394) | Cod sursa (job #2925867) | Cod sursa (job #2723460) | Cod sursa (job #576677) | Cod sursa (job #3195688)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define MaxN 120000
struct st
{
double x,y;
};
st v[MaxN];
vector <st> stiva;
int points;
int findpoint(int n)
{
int pos, i;
pos=0;
for(i=0; i<n; i++)
{
if(v[i].y<v[pos].y || (v[i].y==v[pos].y && v[i].x<v[pos].x))
pos=i;
}
return pos;
}
int orientation(const st& a, const st& b, const st& c)
{
return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
int cmp(const st& a, const st& b)
{
return orientation(v[0], a, b)<0;
}
void inf_convexa(int n)
{
int i;
stiva.push_back(v[0]);
stiva.push_back(v[1]);
for(i=2; i<n; i++)
{
while(stiva.size()>=2 && orientation(stiva[stiva.size()-2], stiva.back(), v[i])>=0)
{
stiva.pop_back();
}
stiva.push_back(v[i]);
}
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n, i;
in>>n;
for(i=0; i<n; i++)
{
in>>v[i].x>>v[i].y;
}
swap(v[0], v[findpoint(n)]);
sort(v+1, v+n, cmp);
inf_convexa(n);
out<<stiva.size()<<'\n';
for(const st& p: stiva)
{
out<<p.x<<" "<<p.y<<'\n';
}
return 0;
}