Pagini recente » Clasamentul arhivei ACM | Cod sursa (job #2638324) | Cod sursa (job #2802715) | Cod sursa (job #3143326) | Cod sursa (job #3299494)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct ura
{
double x, y;
} v[120002], stiva1[120002], stiva2[120002];
double arie (double xa,double xb,double xc,double ya,double yb,double yc)
{
/*if ((xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya)>=0)
return true;
return false;*/
return xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya;
}
bool cmp (ura a, ura b)
{
if(a.x < b.x){
return true;
}else{
if(a.x == b.x){
if(a.y < b.y){
return true;
}
return false;
}
return false;
}
}
int main()
{
int n;
f>>n;
for (int i=1; i<=n; i++)
f>>v[i].x>>v[i].y;
sort (v+1,v+n+1, cmp);
ura st=v[1], dr=v[n];
int sp1=1, h=0;
stiva1[1]=st;
for (int i=2; i<=n; i++)
{
if (arie(st.x, dr.x, v[i].x, st.y, dr.y, v[i].y)<=0) //dedesubt
{
while (sp1>1&&arie(stiva1[sp1-1].x, stiva1[sp1].x, v[i].x, stiva1[sp1-1].y, stiva1[sp1].y, v[i].y)<=0)
{
sp1--;
}
sp1++;
stiva1[sp1]=v[i];
}
}
h+=sp1;
int sp2=1;
stiva2[sp2] = dr;
for (int i=n-1; i>=1; i--) //deasupra
{
if (arie(st.x, dr.x, v[i].x, st.y, dr.y, v[i].y)>=0)
{
while (sp2>1&&arie(v[i].x, stiva2[sp2].x, stiva2[sp2 - 1].x, v[i].y, stiva2[sp2].y, stiva2[sp2 - 1].y)>0)
{
sp2--;
}
sp2++;
stiva2[sp2]=v[i];
}
}
h+=sp2;
g<<h - 2<<endl;
g<<setprecision(6)<<fixed;
for (int i=2; i<=sp1; i++)
g<<stiva1[i].x<<" "<<stiva1[i].y<<endl;
for (int i=2; i<=sp2; i++)
g<<stiva2[i].x<<" "<<stiva2[i].y<<endl;
return 0;
}