Pagini recente » Cod sursa (job #2982391) | Cod sursa (job #1187493) | Cod sursa (job #1241957) | Cod sursa (job #2955183) | Cod sursa (job #2768432)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
};
punct v[120005];
punct pt= {1e9+7,1e9+7};
int n,nr;
punct rasp[120005];
bool comp(punct a, punct b)
{
///(a.y-pt.y)/(a.x-pt.x)<(b.y-pt.y)/(b.x-pt.x)
///(a.y-pt.y)*(b.x-pt.x)<(b.y-pt.y)*(a.x-pt.x)
if(a.x==pt.x && a.y==pt.y) return 1;
if(b.x==pt.x && b.y==pt.y) return 0;
return ( (a.y-pt.y)*(b.x-pt.x)-(b.y-pt.y)*(a.x-pt.x)<0 );
}
bool in_exterior(punct a, punct b, punct p)
{
if(a.x<b.x)
{
double gr=(b.y-a.y)/(b.x-a.x);
double h=b.y-gr*b.x;
if(gr*p.x+h>=p.y) return 1;
return 0;
}
else if(a.x>b.x)
{
double gr=(b.y-a.y)/(b.x-a.x);
double h=b.y-gr*b.x;
if(gr*p.x+h<=p.y) return 1;
return 0;
}
else
{
if(a.y<b.y)
{
if(p.x>=a.x) return 1;
return 0;
}
else if(a.y>b.y)
{
if(p.x<=a.x) return 1;
return 0;
}
}
}
int main()
{
fin>>n;
for(int i=0; i<n; i++)
{
fin>>v[i].x>>v[i].y;
if(pt.x>v[i].x) pt=v[i];
else if(pt.x==v[i].x && pt.y>v[i].y) pt=v[i];
}
sort(v,v+n,comp);
for(int i=0; i<n; i++)
{
//cout<<v[i].x<<" "<<v[i].y<<"\n";
}
rasp[nr++]=v[0];
rasp[nr++]=v[1];
for(int i=2; i<n; i++)
{
punct a=rasp[nr-2];
punct b=rasp[nr-1];
while(nr>1 && in_exterior(a,b,v[i]))
{
//cout<<a.x<<" "<<a.y<<": "<<b.x<<" "<<b.y<<": "<<v[i].x<<" "<<v[i].y<<"\n";
nr--;
a=rasp[nr-2];
b=rasp[nr-1];
}
rasp[nr++]=v[i];
}
fout<<nr<<"\n";
for(int i=0; i<nr; i++) fout<<fixed<<setprecision(6)<<rasp[i].x<<" "<<rasp[i].y<<"\n";
return 0;
}