Pagini recente » Monitorul de evaluare | Cod sursa (job #363729) | Cod sursa (job #3172813) | Cod sursa (job #1849090) | Cod sursa (job #2190285)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define DIM 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N, top, origin;
typedef struct point{
double x, y;
} point;
point P[DIM], S[DIM];
int cadran(point A){
if(A.x >= 0 && A.y >= 0)
return 1;
if(A.x < 0 && A.y >= 0)
return 2;
if(A.x < 0 && A.y < 0)
return 3;
if(A.x >= 0 && A.y < 0)
return 4;
}
double det(point A, point B, point C){
return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
int cmp(point A,point B){
int CadranA = cadran(A);
int CadranB = cadran(B);
if(CadranA < CadranB)
return 1;
if(CadranA > CadranB)
return 0;
return det(P[origin], A, B) > 0;
}
int main(){
fin >> N;
fin >> P[0].x >> P[0].y;
for(int i = 1; i < N ;i ++){
fin >> P[i].x >> P[i].y;
if(P[origin].x > P[i].x || (P[origin].x == P[i].x && P[origin].y > P[i].y))
origin = i;
}
swap(P[0], P[origin]);
sort(P + 1, P + N, cmp);
S[1] = P[0];
S[2] = P[1];
top = 2;
for(int i = 2; i < N; i ++){
while(top >= 2 && det(S[top - 1], S[top], P[i]) < 0)
top --;
S[++ top] = P[i];
}
fout << top << "\n";
for(int i = 1; i <= top; i ++)
fout << fixed << setprecision(6) << S[i].x << " " << S[i].y << "\n";
fin.close();
fout.close();
return 0;
}