Pagini recente » Cod sursa (job #1104042) | Cod sursa (job #1539809) | Cod sursa (job #2042568) | Cod sursa (job #3194087) | Cod sursa (job #2003627)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct {
float x,y;
} a[120001],S[120001];
int n,vf;
double unghi(Punct a, Punct b, Punct c){
return (b.y - a.y) * (c.x - a.x) - (c.y - a.y) * (b.x - a.x);
}
bool cmp(Punct x, Punct b){
return (unghi(a[1],x,b) > 0);
}
void PUSH(Punct P)
{
vf++;
S[vf]=P;
}
void POP()
{
vf--;
}
float Produs(Punct P1, Punct P2,Punct P3)
{
return (P2.x-P1.x)*(P3.y-P1.y)-(P3.x-P1.x)*(P2.y-P1.y);
}
int main()
{
f>>n;
for(int i=1;i<=n;++i)
f>>a[i].x>>a[i].y;
int poz=1;
for(int i = 1; i <= n; ++i)
if(a[i].x < a[poz].x || (a[i].x == a[poz].x && a[i].y < a[poz].y))
poz = i;
swap(a[1],a[poz]);
sort(a + 2, a + n + 1, cmp);
vf=0;
PUSH(a[1]);
PUSH(a[2]);
for(int i = 3; i <= n; ++i){
while(vf >= 2 && unghi(S[vf - 1], S[vf], a[i]) < 0)
--vf;
PUSH(a[i]);
}
g<<vf<<'\n';
for(int i=vf;i>=1;--i)
g<<fixed<<setprecision(6)<<S[i].x<<" "<<S[i].y<<'\n';
return 0;
}