Pagini recente » Cod sursa (job #3174240) | Cod sursa (job #2518417) | Cod sursa (job #2513689) | Cod sursa (job #2965142) | Cod sursa (job #1883011)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 120005;
int N,poz,wx,wy,top;
inline int cross_product(double x1,double y1,double x2,double y2,double x3,double y3){
return (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
}
struct el{
double x,y;
bool operator <(const el&A) const
{
return (cross_product(wx,wy,x,y,A.x,A.y)<0);
}
}a[nmax],st[nmax];
inline void Solve(){
int i;
top = 2;
st[1] = a[1];
st[2] = a[2];
for(i = 3; i <= N; ++i){
while(top >= 2 && cross_product(st[top-1].x,st[top-1].y,st[top].x,st[top].y,a[i].x,a[i].y)>0)
--top;
st[++top] = a[i];
}
}
int main(){
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i;
f >> N;
for(i = 1; i <= N; ++i)
f >> a[i].x >> a[i].y;
poz = 1;
for(i = 2; i <= N; ++i)
if(a[i].x < a[poz].x)
poz = i;
swap(a[1],a[poz]);
wx = a[1].x , wy = a[1].y;
sort(a+2,a+N+1);
Solve();
g << top << '\n';
for(i = top; i; --i)
g <<fixed <<setprecision(6) << st[i].x << ' ' << st[i].y << '\n';
// for(i = 1; i <= N; ++i)
// cout << a[i].x <<' '<< a[i].y << '\n';
f.close();
g.close();
return 0;
}