Pagini recente » Cod sursa (job #1072602) | Cod sursa (job #1891772) | Cod sursa (job #2729812) | Cod sursa (job #1474072) | Cod sursa (job #2630219)
#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(){}
};
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,minpoz;
pct a[120005];
vector <pct> v,con;
bool comp(pct x, pct y)
{
return (x.y-a[minpoz].y)*(y.x-a[minpoz].x) < (y.y-a[minpoz].y)*(x.x-a[minpoz].x);
}
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;
minpoz=1;
for(i=2;i<=n;i++)
{
if(a[i].x==a[minpoz].x && a[i].y<a[minpoz].y)
minpoz=i;
if(a[i].x<a[minpoz].x)
minpoz=i;
}
con.push_back(a[minpoz]);
for(i=1;i<=n;i++)
{
if(i==minpoz)
continue;
v.push_back(a[i]);
}
sort(v.begin(), v.end(), comp);
for(pct it : v)
add(it);
fout.precision(12);
fout<<fixed;
fout<<con.size()<<'\n';
for(pct it : con)
fout<<it.x<<' '<<it.y<<'\n';
return 0;
}