Pagini recente » Cod sursa (job #73722) | Cod sursa (job #1677766) | Cod sursa (job #1018771) | preONI 2008 - Clasament Runda 2, Clasa a 9-a | Cod sursa (job #1431161)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *fin = fopen("infasuratoare.in" ,"r");
FILE *fout= fopen("infasuratoare.out","w");
int N;
const int Nmax = 120010;
struct Point{
double x, y;
} P[Nmax];
vector <int> Stack;
void SetUp(){
fscanf(fin, "%d", &N);
for(int i = 1; i <= N; i ++)
fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
return;
}
inline double Area(Point &P1, Point &P2, Point &P3){
return
+ P1.x * P2.y - P1.y * P2.x
+ P2.x * P3.y - P2.y * P3.x
+ P3.x * P1.y - P3.y * P1.x;
}
inline int cmp(Point P1, Point P2){
return Area(P[1], P1, P2) > 0;
}
void CodeExpert(){
for(int i = 2; i <= N; i ++){
if(P[1].x > P[i].x)
swap(P[1], P[i]);
}
sort(P + 1, P + N + 1, cmp);
Stack.push_back(1);
for(int i = 2; i <= N; i++){
while(Stack.size() > 1 && (Area(P[Stack[Stack.size() - 2]], P[Stack[Stack.size() - 1]] , P[i])) <= 0)
Stack.pop_back();
Stack.push_back(i);
}
fprintf(fout, "%d\n", Stack.size());
for(int i = 0; i < Stack.size(); i ++)
fprintf(fout, "%.12f %.12f\n", P[Stack[i]].x, P[Stack[i]].y);
return;
}
int main(){
SetUp();
CodeExpert();
return 0;
}