Pagini recente » Cod sursa (job #944830) | Cod sursa (job #1681665) | Cod sursa (job #935041) | Cod sursa (job #2238917) | Cod sursa (job #2712465)
#include <bits/stdc++.h>
#define inf 1000999090
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
long double x,y;
}v[120100],s[120100];
int compare(punct A, punct B)
{
/// m1 = (A.x-v[1].x) / (A.y-v[1].y) -> panta lui A fata de primul punct
/// m2 = (B.x-v[1].x) / (B.y-v[1].y) -> panta lui A fata de primul punct
/// corect este return(m1>m2)
/// dar nu comparam rapoarte, ci produse pe diagonala
return ((A.x - v[1].x) * (B.y - v[1].y) > (A.y-v[1].y) * (B.x - v[1].x));
}
int viraj_dreapta(punct A, punct B, punct C)
{
/// se face determinant:
/// A.x A.y 1
/// B.x B.y 1
/// C.x C.y 1
/// daca valoarea este negativa sau egala cu 0 => viraj dreapta
/// asa e formula - o iei ca atare
/// e putin tricky atunci cand determinantul este 0 => punctele sunt coliniare
/// pot aparea prob. in cazul asta
/// dar ni se garanteaza ca nu vor exista puncte coliniare in aceasta problema
return((A.x*B.y + B.x*C.y + A.y*C.x - B.y*C.x - C.y*A.x - A.y*B.x) <= 0);
}
int n,i,minix=inf,miniy=inf,poz,T;
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if(v[i].x<minix)
{
minix=v[i].x;
miniy=v[i].y;
poz=i;
}
else if(v[i].x==minix)
{
if(v[i].y<miniy)
{
miniy=v[i].y;
poz=i;
}
}
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,compare);
/// punem in stiva primele doua puncte
s[1]=v[1];
s[2]=v[2];
T=2;
for(i=3;i<=n;i++)
{
/// eliminam cat putem (trb. totusi sa avem minim 2 puncte) si cat timp obtinem "viraj" la dreapta
/// in viraj_dreapta() conteaza ordinea -> pentru ca noi comparam punctul curent cu un vector, unde este important si sensul
while(T>2 && viraj_dreapta(s[T-1],s[T],v[i]))T--;
T++;
s[T]=v[i];
}
g<<T<<'\n';
for(i=1;i<=T;i++)
g<<fixed<<setprecision(12)<<v[i].x<<" "<<fixed<<setprecision(12)<<v[i].y<<'\n';
return 0;
}