UVa : 855 (Lunch in Grid City)


1. Copied the algorithm from jan vai 🙂

2. what i understand ..
we all know that the median is
suppose, u r given ‘n’ numbers in an array p []
if ( n == odd ) median = p [n / 2]
else median = p [(n – 1) / 2]

3. now we r given a 2d plane
and we need to find the median separately
all the values of street are saved in array p
all the values of avenue are saved in array q
sort p and q
then output the median

Solution:

// http://uva.onlinejudge.org/external/8/855.html
// Runtime : 0.044s
// Tag : median

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int main ()
{
	int testCase;
	scanf ("%d", &testCase);

	while ( testCase-- ) {
		int s, a, f;
		scanf ("%d %d %d", &s, &a, &f);

		int p [50000 + 5];
		int q [50000 + 5];

		for ( int i = 0; i < f; i++ )
			scanf ("%d %d", &p [i], &q [i]);

		sort (p, p + f);
		sort (q, q + f);

		if ( f % 2 ) printf ("(Street: %d, Avenue: %d)\n", p [f / 2], q [f / 2]);
		else printf ("(Street: %d, Avenue: %d)\n", p [(f - 1) / 2], q [(f - 1) / 2]);
	}

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s