Cod sursa(job #3315957)

Utilizator David_RadavoiRadavoi David Alexandru David_Radavoi Data 16 octombrie 2025 16:50:12
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

#define MAXN 120000

int stiva1[MAXN + 1];
int stiva2[MAXN + 1];
int vf1, vf2;

struct infasor{
	float x, y;
}v[MAXN + 1];

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

int aria(float xa, float ya, float xb, float yb, float xc, float yc){
	float arie = xa * yb + xb * yc + xb * ya - xc * yb - xa * yc - xb * ya;
	if (arie < 0){
		return -1;
	}
	return 1;
}

int main()
{
    FILE *fin, *fout;
    fin = fopen("infasuratoare.in", "r");
    fout = fopen("infasuratoare.out", "w");
    int N, i;
    fscanf(fin, "%d", &N);
    for (i = 1; i <= N; i++){
		fscanf(fin, "%f%f", &v[i].x, &v[i].y);
    }
    sort(v + 1, v + N + 1, cmp);
    vf1 = vf2 = 1;
    stiva1[vf1] = stiva2[vf2] = 1;
    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 || i == N){
			while (vf1 > 1 && aria(v[stiva1[vf1 - 1]].x, v[i].x, v[i].y, v[stiva1[vf1 - 1]].y, v[stiva1[vf1]].x, v[stiva1[vf1]].y) < 0){
				vf1--;
			}
			stiva1[++vf1] = i;
		}
		if (aria(v[1].x, v[1].y, v[N].x, v[N].y, v[i].x, v[i].y) > 0 || i == N){
			while (vf2 > 1 && aria(v[stiva2[vf2 - 1]].x, v[stiva2[vf2 - 1]].y, v[i].x, v[i].y, v[stiva2[vf2]].x, v[stiva2[vf2]].y) > 0){
				vf2--;
			}
			stiva2[++vf2] = i;
		}
    }
    fprintf(fout, "%d\n", vf1 + vf2 - 2);
    for (i = 1; i <= vf1; i++){
		fprintf(fout, "%f %f\n", v[stiva1[i]].x, v[stiva1[i]].y);
    }
    for (i = 2; i < vf2; i++){
		fprintf(fout, "%f %f\n", v[stiva2[i]].x, v[stiva2[i]].y);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}