Pagini recente » Cod sursa (job #3332710) | Cod sursa (job #2505693) | Cod sursa (job #3338636) | Cod sursa (job #468498) | Cod sursa (job #3344415)
#include <bits/stdc++.h>
#define VMAX 200005
#define INF 1e10
#define int long long int
#define double long double
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct pct{
double i,j;
pct (double i_=0,double j_=0): i(i_),j(j_) {};
};
vector<pct> numere;
vector<int> luate;
double arie(pct a, pct b, pct c)
{
return a.i*b.j+b.i*c.j+c.i*a.j-a.i*c.j-b.i*a.j-c.i*b.j;
}
bool comp(pct a, pct b)
{
return arie(numere[0],a,b)>0;
}
signed main()
{
ios_base::sync_with_stdio(0);
int n,m,i,j,k,t,nr,minim,maxim,suma,st,dr,mij;
double p,q;
fin>>n;
for(i=0;i<n;i++)
{
fin>>p>>q;
numere.push_back(pct(p,q));
if(numere[i].i<numere[0].i || numere[i].i==numere[0].i && numere[i].j<numere[0].j)
{
swap(numere[0],numere[i]);
}
}
sort(numere.begin()+1,numere.end(),comp);
luate.push_back(0);
for(i=1;i<numere.size();i++)
{
while(luate.size()>=2 && arie(numere[luate[luate.size()-2]],numere[luate[luate.size()-1]],numere[i])<0)
luate.pop_back();
luate.push_back(i);
}
fout<<luate.size()<<'\n';
for(auto it:luate)
fout<<fixed<<setprecision(7)<<numere[it].i<<' '<<numere[it].j<<'\n';
return 0;
}