Pagini recente » Cod sursa (job #3198512) | Cod sursa (job #239077) | Cod sursa (job #2932495) | Cod sursa (job #104961) | Cod sursa (job #1971264)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define nMax 120001
#define pb push_back
#define mkp make_pair
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
pair<double, double> pct[nMax], stck[nMax];
double det(const pair<double, double> &a, const pair<double, double> &b, const pair<double, double> &c)
{
return a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-a.y*b.x-a.x*c.y;
}
bool cmp(const pair<double, double> &a, const pair<double, double> &b)
{
return det(pct[1], a, b)>0;
}
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
fin>>pct[i].x>>pct[i].y;
int poz=1;
for(int i=2; i<=n; i++)
if(pct[i]<pct[poz])
poz=i;
swap(pct[1], pct[poz]);
sort(pct+2, pct+n+1, cmp);
int top=0;
stck[++top]=pct[1];
stck[++top]=pct[2];
for(int i=3; i<=n; i++)
{
while(top>=2 && det(stck[top-1], stck[top], pct[i])<0)
top--;
stck[++top]=pct[i];
}
fout<<top<<'\n';
for(int i=1; i<=top; i++)
fout<<fixed<<setprecision(6)<<stck[i].x<<" "<<stck[i].y<<'\n';
}