Pagini recente » Cod sursa (job #2206141) | Cod sursa (job #2292477) | Cod sursa (job #160710) | Cod sursa (job #2807713) | Cod sursa (job #2371367)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
stack <int> q;
struct pct
{
double x,y;
double tg;
int ct;
} a[120001],b[120001];
int n;
void citire()
{
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>a[i].x>>a[i].y;
a[i].ct=i;
}
}
bool comp(pct a,pct b)
{
return a.x < b.x||(a.x == b.x && a.y < b.y);
}
bool orientare(pct a,pct b,pct c)
{
return (a.y - b.y)*(a.x -c .x)<(a.x - b.x)*(a.y - c.y);
}
bool comppant(pct c, pct d)
{
return orientare(a[1],c,d);
}
int main()
{
citire();
sort(a+1,a+n+1,comp);
sort(a+2,a+n+1,comppant);
q.push(1);
q.push(2);
int x,y;
for(int i=3; i<=n; i++)
{y=q.top();
q.pop();
x=q.top();
q.pop();
while(orientare(a[x],a[y],a[i])==false)
{y=x;
x=q.top();
q.pop();
}
q.push(x);
q.push(y);
q.push(i);
}
fout<<q.size()<<"\n";
int ct=0;
while(q.empty()==false)
{//fout<<fixed<<setprecision(6)<<a[q.top()].x<<" "<<a[q.top()].y<<"\n";
ct++;
b[ct]=a[q.top()];
q.pop();
}
for(int i=ct;i>=1;i--)
fout<<fixed<<setprecision(6)<<b[i].x<<" "<<b[i].y<<"\n";
return 0;
}