Pagini recente » Cod sursa (job #193793) | Clasament 321 | Cod sursa (job #1907089) | Cod sursa (job #1657207) | Cod sursa (job #2519330)
#include <bits/stdc++.h>
#define MAX_NR 1000000100
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x,y;
}v[120100],s[120100];
int compare(punct A,punct B)
{
/// panta1 = (A.x-v[1].x)/(A.y-v[1].y)
/// panta2 = (B.x-v[1].x)/(B.y-v[1].y)
/// cand compar fac produs pe diagonala pentru precizie mai mare
return((A.x-v[1].x)*(B.y-v[1].y)>(A.y-v[1].y)*(B.x-v[1].x));
}
bool viraj_dreapta(punct A,punct B,punct C)
{
/// folosim formula cu determinant
/// (A.x A.y 1)
/// (B.x B.y 1)
/// (C.x C.y 1)
/// acest determinant da semn -1 daca punctul C se afla in dreapta vectorului AB, respectiv semn +1 daca e in stanga
/// IMPORTANT! este dreapta vectorului, adica este important si sensul
return ((A.x*B.y + B.x*C.y + A.y*C.x - B.y*C.x - C.y*A.x - B.x*A.y)<0);
}
int n,i,poz,T;
double minix=MAX_NR,miniy=MAX_NR;
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
/// cautam un punct care sigur e pe infasuratoare -> cel mai din stanga iar in caz de egalitate, cel mai de jos
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;
}
}
}
/// il punem pe pozitia 1 pe acel punct aflat anterior
swap(v[1],v[poz]);
/// sortam dupa panta pe care o formeaza punctul ales cu puntele celelalte
sort(v+2,v+n+1,compare);
/// pun primele 2 puncte in stiva
T=2;
s[1]=v[1];
s[2]=v[2];
/// parcurg punctele in ordine
for(i=3;i<=n;i++)
{
/// daca virez la stanga, atunci pun punctul
/// daca virez la dreapta, atunci scot din stiva pana cand obtin viraj la stanga
/// virez la st/dr daca punctul "i" se afla pe partea negativa, respectiv pozitia a dreptei determinata de primele 2 puncte din varful stivei
/// la "viraj_dreapta" apelez neaparat in ordinea asta pentru ca ma intereseaza sensul dreptei
while(T>2 && viraj_dreapta(s[T-1],s[T],v[i]))T--;
T++;s[T]=v[i];
}
/// programul afiseaza deja in ordine trigonometrica
g<<T<<'\n';
for(i=1;i<=T;i++)
g<<fixed<<setprecision(6)<<s[i].x<<" "<<fixed<<setprecision(6)<<s[i].y<<'\n';
return 0;
}