Pagini recente » Cod sursa (job #976724) | Cod sursa (job #1026366) | Cod sursa (job #2260421) | Cod sursa (job #1682618) | Cod sursa (job #3186235)
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <iomanip>
#define nmx 120005
using namespace std;
int n,i2;
double xm,ym,x,y;
struct edge
{
double x,y;
};
vector <edge> v;
bool cmp(edge a,edge b)
{
return ((a.y-ym)*(b.x-xm)<(a.x-xm)*(b.y-ym));
}
deque <edge> dq;
bool orientation(edge a,edge b,edge c)
{
double nr=a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
if (nr>0) return 1;
return 0;
}
int main()
{
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
f>>n;
ym=1000000005;
for (int i=1; i<=n; i++)
{
f>>x>>y;
if (y<ym)
{
ym=y;
xm=x;
i2=i;
}
v.push_back({x,y});
}
for (int i=0;i<n;i++)
if (v[i].x==xm && v[i].y==ym) swap(v[0],v[i]);
sort (v.begin()+1,v.end(),cmp);
dq.push_front(v[0]);
dq.push_front(v[1]);
for (int i=2; i<n; i++)
{
edge a,b,c;
c=v[i];
b=dq.front();
dq.pop_front();
a=dq.front();
if (orientation(a,b,c))
{
cout<<i<<' ';
dq.push_front(b);
dq.push_front(c);
}
else
{
dq.push_front(c);
}
}
g<<dq.size()<<'\n';
g<<fixed<<setprecision(6);
while (dq.size()>0)
{
auto u=dq.back();
dq.pop_back();
g<<u.x<<' '<<u.y<<'\n';
}
}