Pagini recente » Cod sursa (job #1952473) | Cod sursa (job #1690812) | Cod sursa (job #1478414) | Cod sursa (job #936942) | Cod sursa (job #2630206)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct pct
{
long double x, y;
pct(long double x, long double y)
{
this->x=x;
this->y=y;
}
pct(){}
bool operator<(pct b) const
{
if(x==b.x)
return x<b.x;
return y<b.y;
}
bool operator==(pct b)
{
return (x==b.x && y==b.y);
}
};
long double prod(pct a, pct b, pct c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int n,i;
pct mini;
pct a[120005];
vector <pct> v,con;
bool comp(pct a, pct b)
{
return prod(pct(0, 0), mini, a) <= prod(pct(0,0), mini, b);
}
void add(pct x)
{
while(con.size()>=2)
{
if(prod(con[con.size()-2], con.back(), x)<=0)
con.pop_back();
else
break;
}
con.push_back(x);
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i].x>>a[i].y;
mini=pct(1e9, 1e9);
for(i=1;i<=n;i++)
mini=min(mini, a[i]);
con.push_back(mini);
for(i=1;i<=n;i++)
{
if(a[i]==mini)
continue;
v.push_back(a[i]);
}
sort(v.begin(), v.end(), comp);
for(pct it : v)
add(it);
fout<<con.size()<<'\n';
for(pct it : con)
fout<<it.x<<' '<<it.y<<'\n';
return 0;
}