Pagini recente » Cod sursa (job #44492) | Cod sursa (job #1389125) | Cod sursa (job #365124) | Cod sursa (job #3154130) | Cod sursa (job #2628419)
#include <bits/stdc++.h>
using namespace std;
ifstream r("infasuratoare.in");
ofstream w("infasuratoare.out");
struct Point
{
double x, y;
};
vector<Point>v;
Point g[120005];
int cnt;
double prod(Point a, Point b, Point c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(Point a, Point b)
{
return prod(g[1], a, b) < 0;
}
int main()
{
r>>cnt;
for(int i = 1; i <= cnt; ++i)
{
r>>g[i].x>>g[i].y;
}
int pos = 1;
for(int i = 2; i <= cnt; ++i)
{
if(g[i].x > g[pos].x)
{
continue;
}
if(g[i].x < g[pos].x)
{
pos = i;
continue;
}
if(g[i].y < g[pos].y)
{
pos = i;
}
}
swap(g[1], g[pos]);
sort(g+2, g+cnt+1, cmp);
v.push_back(g[1]);
v.push_back(g[2]);
for(int i = 3; i <= cnt; ++i)
{
while(v.size() >= 2 && prod(v[v.size() - 2], v[v.size() - 1], g[i]) > 0)
{
v.pop_back();
}
v.push_back(g[i]);
}
w<<fixed<<v.size()<<"\n";
while(!v.empty() )
{
w<<setprecision(13)<<v[v.size() - 1].x <<" "<< v[v.size() - 1].y <<"\n";
v.pop_back();
}
return 0;
}