Cod sursa(job #245973)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 19 ianuarie 2009 16:46:10
Problema Gropi Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.58 kb
#include<stdio.h>
#define infile "gropi.in"
#define outfile "gropi.out"
#define nmax (100*1000+1)
struct gropi
	{
	int i,j; //coordonatele gropii
	int p; //numarul de schimbari de directie de la groapa 1 pana la aceasta groapa
	} v[nmax]; //aici vom salva fiecare gropa
int c; //numarul de coloane al drumului (linii are doua)
int n; //numarul de gropi

//citim gropile
void citire(struct gropi v[nmax], int *n, int *c)
	{
	int i;
	scanf("%d %d\n",c,n);
	for(i=1;i<=*n;i++) scanf("%d %d\n",&v[i].i,&v[i].j); //citim si salvam fiecare groapa
	}

//plasam elementul de la pozitia p, la pozitia sa corecta, si o returnam (pozitia)
int divide(struct gropi v[nmax], int p, int q)
	{
	struct gropi aux=v[p];
	while(p<q)
		{
		//va fi nevoie sa comparam doar coloana (j) deoarece pe aceeasi coloana nu pot fi doua gropi :P
		while(p<q && v[q].j>=aux.j) q--; //cat timp cele din dreapta sunt mai mari
		v[p]=v[q]; //am gasit unul mai mic, il mutam in partea stanga
		while(p<q && v[p].j<=aux.j) p++; //cat timp cele din stanga sunt mai mici
		v[q]=v[p]; //am gasit unul mai mare, il mutam in partea dreapta
		}
	v[p]=aux; //punem elementul la pozitia lui
	return p; //returnam pozitia
	}

//sorteaza [p,q] in functie de v[i].j
void qsort(struct gropi v[nmax], int p, int q)
	{
	int m=divide(v,p,q); //plasam pe p la locul lui
	if(m-1>p) qsort(v,p,m-1); //sortam partea stanga
	if(m+1<q) qsort(v,m+1,q); //sortam partea dreapta
	}

//aceasta functie salveaza pt fiecare groapa de cate ori a fost nevoit soferul ca pana la ea sa schimbe directia (de la pozitia 1)
void fai_schimbari(struct gropi v[nmax], int n)
	{
	int i;
	v[1].p=1;
	for(i=2;i<=n;i++)
		if(v[i].i==v[i-1].i) v[i].p=v[i-1].p; //groapa se afla pe aceeasi linie, deci nu se schimba directia
		else v[i].p=v[i-1].p+1; //groapa se afla pe alta linie, deci se schimba directia
	}

//calculam distanta dintre s si f
int calculeaza_distanta(struct gropi v[nmax], int n, struct gropi s, struct gropi f)
	{
	int p,q;
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(v,&n,&c); //citim gropile din fisier
qsort(v,1,n); //sortam coordonatele gropilor
fai_schimbari(v,n); //salvam numarul de schimbari de directie pt fiecare groapa

struct gropi s,f,aux;
int m;
scanf("%d\n",&m);
while(m) //luam fiecare drum in parte
	{
	scanf("%d %d %d %d\n",&s.i,&s.j,&f.i,&f.j); //citim coordonatele pt start si pt sfarsit
	if(f.j<s.j) { aux=s; s=f; f=aux; } //schimbam startul cu finalul, a.i. sa avem coloana minima in s, si cealalta in f
	m--;
	}

fclose(stdin);
fclose(stdout);
return 0;
}