2702 - Counting Intersections

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

2702 - Counting Intersections

Post by ymondelo20 » 5 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

HaZard
Posts: 115
Joined: 5 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2702 - Counting Intersections

Post by HaZard » 5 years ago

Hola a todos, este ejercicio me ha dado varios WA, pero tiro el codigo contra el datagen y no le encuentro respuestas mal, excepto con coordenadas negativas, pero en la especificacion del problema no dice que hayan, ¿pueden ayudarme?

Este es el codigo:

Code: Select all

#include <algorithm>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <iostream>

using namespace std;

struct iii {
	int v, a, b;
} ;
vector <iii> x[50005];
vector <iii> y;

bool mark[50005];

int n, v, a, b, answ = 0;
char c;

bool cross(iii p1, iii p2) {
	if(p2.a <= p1.v && p1.v <= p2.b) {
		if(p1.a <= p2.v && p2.v <= p1.b) {
			return true;
		}
	}
	return false;
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> c >> v >> a >> b;
		if(c == 'V') {
			x[v].push_back((iii) { v, a, b });
		}
		else
			y.push_back((iii) { v, a, b });
	}

	for(int i = 0; i < (int)y.size(); i++) {
        for(int j = y[i].a; j <= y[i].b; j++) {
            for(int k = 0; k < (int)x[j].size(); k++) {
                if(cross(y[i], x[j][k]))
                    answ++;
            }
        }
	}

	printf("%d\n", answ);
}
Last edited by HaZard on Sat Dec 06, 2014 10:55 am, edited 1 time in total.
teruel

legar
Posts: 1
Joined: 5 years ago
Gender: None specified

Re: 2702 - Counting Intersections

Post by legar » 5 years ago

El problema es que no siempre en la entrada el valor inicial de cada segmento es el menor entre los dos, ademas tu solucion es muy lenta, debes pensar en algo mas rapido.

HaZard
Posts: 115
Joined: 5 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2702 - Counting Intersections

Post by HaZard » 5 years ago

No me habia dado cuenta de eso, gracias por la ayuda, pensaré en algo que sea más rápido.
teruel

Post Reply

Return to “Problem set”