Pagini recente » Cod sursa (job #82791) | Cod sursa (job #2148266) | Cod sursa (job #3345773) | Cod sursa (job #74244) | Cod sursa (job #3353328)
/*
* author [dubit]
*/
#include <bits/stdc++.h>
using namespace std;
struct point{
double x,y;
};
point origin={0,0};
double det(point a,point b,point c) // Determinantul (produs vectorial). Semnul indica orientarea
{ // >0 viraj la stanga; <0 viraj la dreapta; =0 coliniar
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dist(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(point a,point b)
{
double d=det(origin,a,b);
if(d)
return d>0;
return dist(origin,a)>dist(origin,b);
}
point v[120005];
int n,minimizedpoint;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
v[0]={1000000005,1000000005};
for(int i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
if(v[i].y<v[minimizedpoint].y // Cautam punctul minim (cel mai jos si la stanga)
|| (v[i].y==v[minimizedpoint].y && v[i].x<v[minimizedpoint].x) )
minimizedpoint=i;
}
v[0]=v[minimizedpoint]; // In v[0] am retine offset-ul de la minim la origine, dar in problema asta nu am avut nevoie.
swap(v[minimizedpoint],v[1]); //Interschimbam punctul minim cu primul punct
origin=v[1];
sort(v+2,v+n+1,cmp); // Sortam trigonometric
int firstDetNotEqualToZero;
for(firstDetNotEqualToZero=2;firstDetNotEqualToZero<=n;firstDetNotEqualToZero++) // Gasim primul punct necoliniar
if(det(v[1],v[2],v[firstDetNotEqualToZero]))
break;
for(int i=2, j=firstDetNotEqualToZero-1;i<j;i++,j--) //Inversam punctele coliniare cele mai apropiate de pivot pt scanare corecta
swap(v[i],v[j]);
point stk[120005]; // Stiva de puncte pentru determinarea infasuratoarei convexe
int top=2;
stk[1]=v[1];
stk[2]=v[2];
for(int i=3;i<=n;i++)
{
while(top>=2 && det(stk[top-1],stk[top],v[i])<0) // Scoatem punctele care produc viraj la dreapta (strica convexitatea)
top--;
stk[++top]=v[i]; // Adaugam ultimul punct la infasuratoare
}
cout<<top<<'\n';
for(int i=1;i<=top;i++) // Afisam punctele infasuratoarei cu precizia specificata in enunt
cout<<fixed<<setprecision(6)<<stk[i].x<<' '<<stk[i].y<<'\n';
return 0;
}