Pagini recente » Cod sursa (job #428360) | Cod sursa (job #768443) | Cod sursa (job #1352211) | Cod sursa (job #1012422) | Cod sursa (job #2515404)
#include <bits/stdc++.h>
#define NM 120005
#define EPS 1e-9
using namespace std;
struct point
{
long double x, y;
point() {}
point(long double x, long double y): x(x), y(y) {}
point& operator+=(const point &t)
{
x += t.x;
y += t.y;
return *this;
}
point& operator-=(const point &t)
{
x -= t.x;
y -= t.y;
return *this;
}
point operator+(const point &t) const
{
return point(*this) += t;
}
point operator-(const point &t) const
{
return point(*this) -= t;
}
} v[NM], minn, maxx;
long double cross(point A, point B)
{
return A.x*B.y - A.y*B.x;
}
bool cmp(point A, point B)
{
return A.x < B.x || (A.x == B.x && A.y < B.y);
}
bool cmp2(point A, point B)
{
point O = {0, 0};
if(cross(B-O, B-A) < 0)
return 0;
return 1;
}
int n;
vector<point> sol1, sol2;
ifstream fin ("infasuratoare.in");
int main()
{
FILE *fout;
fout = fopen( "infasuratoare.out", "w" );
fin >> n;
for(int i=1; i<=n; i++)
fin >> v[i].x >> v[i].y;
sort(v+1, v+1+n, cmp);
minn = v[0], maxx = v[n];
for(int i=1; i<=n; i++)
{
if(cross(minn-v[i], maxx-v[i]) >= 0)
{
if(sol1.size() > 1)
{
point C = sol1[sol1.size()-1] - sol1[sol1.size()-2];
point D = v[i] - sol1[sol1.size()-1];
while(cross(C, D) > 0 && sol1.size() > 1)
{
sol1.pop_back();
C = sol1[sol1.size()-1] - sol1[sol1.size()-2];
D = v[i]-sol1[sol1.size()-1];
}
}
sol1.push_back(v[i]);
}
else
{
if(sol2.size() > 1)
{
point C = sol2[sol2.size()-1] - sol2[sol2.size()-2];
point D = v[i] - sol2[sol1.size()-1];
while(cross(C, D) < 0 && sol2.size() > 1)
{
sol2.pop_back();
C = sol2[sol2.size()-1] - sol2[sol2.size()-2];
D = v[i] - sol2[sol1.size()-1];
}
}
sol2.push_back(v[i]);
}
}
for(auto it:sol2)
sol1.push_back(it);
fprintf(fout, "%d\n", sol1.size());
sort(sol1.begin(), sol1.end(), cmp2);
for(int i=0; i<sol1.size(); i++)
{
fprintf(fout,"%.12Lf", sol1[i].x);
fprintf(fout, " ");
fprintf(fout,"%.12Lf\n", sol1[i].y);
}
fclose( fout );
return 0;
}