Pagini recente » Cod sursa (job #2121528) | Cod sursa (job #1438197) | Cod sursa (job #649147) | Cod sursa (job #889184) | Cod sursa (job #2552569)
#include<bits/stdc++.h>
#define nmax 120001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, topleft, topright;
struct coord {
double x,y;
} v[nmax], jos ,sus ,stleft[nmax], stright[nmax];
double arie(coord a,coord b,coord c) {
double q = a.x * (b.y - c.y) - b.x * (a.y - c.y) + c.x * (a.y - b.y);
if(q > 0)
return 1;
else
if(q < 0)
return -1;
return 0;
}
bool cmp(coord x,coord y) {
if(x.y < y.y)
return true;
else
if(x.y == y.y && x.x < y.x)
return true;
else
return false;
}
int main(){
fin >> n;
jos.x = jos.y = 2000000000;
sus.y = sus.x = -1000000000;
for(int i = 1; i <= n; i ++)
{
fin >> v[i].x >> v[i].y;
if(v[i].y < jos.y || (v[i].y == jos.y && v[i].x < jos.x))
jos = v[i];
if(v[i].y > sus.y || (v[i].y == sus.y && v[i].x > sus.x))
sus = v[i];
}
sort(v + 1, v + n + 1, cmp);
topleft = topright = 1;
stleft[topleft] = v[1];
stright[topright] = v[1];
for(int i = 2; i <= n; i ++)
{
if(arie(jos, sus, v[i]) >= 0){
while(arie(stleft[topleft - 1], stleft[topleft], v[i]) != -1 && topleft > 1)
topleft --;
stleft[++ topleft] = v[i];
}
if(arie(jos, sus, v[i]) <= 0){
while(arie(stright[topright - 1], stright[topright], v[i]) != 1 && topright > 1)
topright --;
stright[++ topright] = v[i];
}
}
fout << setprecision(6) << fixed;
fout << topright + topleft - 2 << '\n';
for(int i = 1; i <= topright; i ++)
fout << stright[i].x << " " << stright[i].y << '\n';
for(int i = topleft - 1; i > 1; i --)
fout<< stleft[i].x<< " " << stleft[i].y << '\n';
return 0;
}