Cod sursa(job #3316975)

Utilizator David_RadavoiRadavoi David Alexandru David_Radavoi Data 21 octombrie 2025 16:05:06
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

#define MAXN 120000

int stiva[MAXN + 1];
int vf;

struct infasor{
	double x, y;
	int parte;
}v[MAXN + 1];

bool cmp(infasor a, infasor b){
	if (a.y < b.y){
		return true;
	}
	if (a.y == b.y && a.x < b.x){
		return true;
	}
	return false;
}

double aria(double xa, double ya, double xb, double yb, double xc, double yc){
	return (xb - xa) * (yc - ya) - (xc - xa) * (yb - ya);
}

int main()
{
    FILE *fin, *fout;
    fin = fopen("infasuratoare.in", "r");
    fout = fopen("infasuratoare.out", "w");
    int N, i, avf;
    fscanf(fin, "%d", &N);
    for (i = 1; i <= N; i++){
		fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
    }
    sort(v + 1, v + N + 1, cmp);
    for (i = 2; i < N; i++){
        if (aria(v[1].x, v[1].y, v[N].x, v[N].y, v[i].x, v[i].y) < 0){
            v[i].parte = 1;
        }
        else if (aria(v[1].x, v[1].y, v[N].x, v[N].y, v[i].x, v[i].y) > 0){
            v[i].parte = 2;
        }
        else{
            v[i].parte = 0;
        }
    }
    stiva[1] = 1;
    vf = 1;
    for (i = 2; i <= N; i++){
        if (v[i].parte == 1 || i == N){
            while (vf > 1 && aria(v[stiva[vf - 1]].x, v[stiva[vf - 1]].y, v[stiva[vf]].x, v[stiva[vf]].y, v[i].x, v[i].y) < 0){
                vf--;
            }
            stiva[++vf] = i;
        }
    }
    avf = vf;
    stiva[vf] = N;
    for (i = N - 1; i >= 1; i--){
        if (v[i].parte == 2 || i == 1){
            while (vf > avf && aria(v[stiva[vf - 1]].x, v[stiva[vf - 1]].y, v[stiva[vf]].x, v[stiva[vf]].y, v[i].x, v[i].y) < 0){
                vf--;
            }
            stiva[++vf] = i;
        }
    }
    fprintf(fout, "%d\n", vf - 1);
    for (i = 1; i < vf; i++){
        fprintf(fout, "%.6lf %.6lf\n", v[stiva[i]].x, v[stiva[i]].y);
    }
    return 0;
}