Pagini recente » Cod sursa (job #2250074) | Cod sursa (job #859856) | Cod sursa (job #2567) | Cod sursa (job #2357880) | Cod sursa (job #2955692)
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXN 120000
#define INF 1000000000
#define EPSILON 0.000000000001
struct coord{
double x, y;
};
coord v[MAXN];
int out[MAXN];
double modul(double a){
if(a < 0){
return -a;
}else{
return a;
}
}
bool Verificare_Unghi_Convex(coord lastlast, coord last, coord next){
double a, b, intersectiex;
if(modul(last.y - lastlast.y) < EPSILON){
if(lastlast.x < last.x){
if(last.y < next.y){
return true;
}else{
return false;
}
}else{
if(next.y < last.y){
return true;
}else{
return false;
}
}
}else if(modul(last.x - lastlast.x) < EPSILON){
if(lastlast.y < last.y){
if(next.x < last.x){
return true;
}else{
return false;
}
}else{
if(last.x < next.x){
return true;;
}else{
return false;
}
}
}else{
a = (last.y - lastlast.y) / (last.x - lastlast.x);
b = last.y - (a * last.x);
intersectiex = (next.y - b) / a;
if(lastlast.y < last.y){
if(intersectiex < next.x){
return false;
}else{
return true;
}
}else{
if(next.x < intersectiex){
return false;
}else{
return true;
}
}
}
}
bool cmp(coord a, coord b){
double tg0a, tg0b;
if(a.y == v[0].y){
if(a.x < v[0].x){
return true;
}else{
return false;
}
}else if(b.y == v[0].y){
if(b.x < v[0].x){
return false;
}else{
return true;
}
}else{
tg0a = (a.x - v[0].x) / (a.y - v[0].y);
tg0b = (b.x - v[0].x) / (b.y - v[0].y);
if(tg0b < tg0a){
return true;
}else{
return false;
}
}
}
int main()
{
FILE *fin, *fout;
int n, i, inext, min, u, io;
fin = fopen("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
min = INF;
for(i = 0; i < n; i++){
fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
if(v[i].y < min){
min = v[i].y;
io = i;
}
}
fclose(fin);
swap(v[io], v[0]);
sort(v + 1, v + n, cmp);
out[0] = 1;
out[1] = 2;
u = 2;
inext = 3;
while((inext % n) != io){
if(Verificare_Unghi_Convex(v[out[u - 1]], v[out[u - 2]], v[inext])){
out[u - 1] = inext;
}else{
out[u] = inext;
u++;
}
inext++;
}
fout = fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", u + 1);
fprintf(fout, "%0.6lf %0.6lf\n", v[0].x, v[0].y);
for(i = 0; i < u; i++){
fprintf(fout, "%0.6lf %0.6lf\n", v[out[i]].x, v[out[i]].y);
}
fclose(fout);
return 0;
}