Pagini recente » Cod sursa (job #2032804) | Cod sursa (job #2796632) | Cod sursa (job #1700752) | Cod sursa (job #1855579) | Cod sursa (job #943009)
Cod sursa(job #943009)
#include<fstream>
#include<algorithm>
using namespace std;
struct pct
{
double x,y;
};
pct a[120001],s[120001];
int i,n,k,x;
double mx,my;
double ar(pct a,pct b,pct c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(pct x,pct y)
{
return ar(a[1],x,y)>0;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> n;
my=1 << 30;
for (i=1;i<=n;i++)
{
f >> a[i].x >> a[i].y;
if ((a[i].y<my) || ((a[i].y==my) && (a[i].x<mx)))
{
x=i;
mx=a[i].x;
my=a[i].y;
}
}
swap(a[1],a[x]);
sort(a+2,a+n+1,cmp);
k=1;
s[1]=a[1];
for (i=2;i<=n;i++)
{
while ((k>1) && (ar(s[k-1],s[k],a[i])<0))
k--;
s[++k]=a[i];
}
g << k << "\n";
for (i=1;i<=k;i++)
g << s[i].x << ' ' << s[i].y << "\n";
return 0;
}