Pagini recente » Cod sursa (job #2024173) | Cod sursa (job #1376029) | Cod sursa (job #2916448) | Cod sursa (job #1556403) | Cod sursa (job #2003628)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <iomanip>
#include <cstring>
#include <fstream>
#define NMax 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct conv{
double x;double y;
}v[NMax],s[NMax];
int n,head;
double unghi(conv a, conv b, conv c){
return (b.y - a.y) * (c.x - a.x) - (c.y - a.y) * (b.x - a.x);
}
bool cmp(conv a, conv b){
return (unghi(v[1],a,b) > 0);
}
void citeste(){
f >> n;
for(int i = 1; i <= n; ++i)
f >> v[i].x >> v[i].y;
}
void infasuratoare(){
int poz = 1;
for(int i = 1; i <= n; ++i)
if(v[i].x < v[poz].x || (v[i].x == v[poz].x && v[i].y < v[poz].y))
poz = i;
swap(v[1],v[poz]);
sort(v + 2, v + n + 1, cmp);
s[1] = v[1];
s[2] = v[2];
head = 2;
for(int i = 3; i <= n; ++i){
while(head >= 2 && unghi(s[head - 1], s[head], v[i]) < 0)
--head;
s[++head] = v[i];
}
}
void scrie(){
g << head <<"\n";
for(int i = head; i >= 1; --i){
g <<fixed <<setprecision(6)<< s[i].x <<" "<< s[i].y <<"\n";
}
}
int main()
{
citeste();
infasuratoare();
scrie();
return 0;
}