Pagini recente » Cod sursa (job #361464) | Cod sursa (job #1713631) | Cod sursa (job #124480) | Cod sursa (job #889664) | Cod sursa (job #2287890)
#include<bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Puncte{
double x,y;}v[120002],s[120002];
int l,n;
double cros(Puncte A,Puncte B,Puncte C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline int cmp(const Puncte& p1, const Puncte& p2) {
return cros(v[1], p1, p2) < 0;
}
void MRGA()
{
for(int i=1;i<=n;++i)
{
while(l>1 && cros(s[l-1],s[l],v[i])<=0)
l--;
s[++l]=v[i];
}
int mic=l;
for(int i=n;i>=1;--i)
{
while(l>mic && cros(s[l-1],s[l],v[i])<=0)
l--;
s[++l]=v[i];
}
l--;
}
int main()
{
f>>n;
for(int i=1;i<=n;++i)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
MRGA();
g<<l<<'\n';
for(int i=1;i<=l;++i)
g<<s[i].x<<' '<<s[i].y<<'\n';
}