10865 - Brownie Points

[pipo]

Hi..

In my thought, I have solved this problem exactly...

But... I got Wrong Answer... why ???

The algorithm is following....

Let's set cx, cy which are given at the center of the input sequence of points for this case...

For All of points(x, y),
if ( cx - x ) * ( cy - y ) == 0 then no count;
else if that is large than 0, then increase score of Stan..
else increase score of Ollie...

and then, just print socre of Stan and Ollie...

why wrong answer ? help me...

[mf]

There can be an overflow in (cx - x) * (cy - y). Use long long's or multiply just the signs of the operands.

[pipo]

Thanks a lot... mf..

Due to you, I got AC...

I didn't think about an overflow...

that's a trick for me..

[Joarder]

Why my code getting WA...???
Plz.... Someone Cheak it...
or Give me some test cases...
here is my code....

Code: Select all

/*
 * File: 10865 - Brownie Points I.cpp
 * Tag: 
 * http://uva.onlinejudge.org/external/108/10865.html


 * Runtime: WA
 * Author: Shoshi
 * Created on August , 2011, : M
 */

#pragma warning (disable : 4786)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#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 INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

using namespace std;

typedef struct node {
	int r,c;
}node;

int main() {
	//freopen ("10865 - Brownie Points I_in.txt", "r", stdin);
	int t,a,b,n,i,s,o;
	node tmn;
	vector<node>v;
	LL m;
	while(cin>>t) 
	{
		if(t == 0)
			break;
		n=t;
		v.clear();
		while(t--) 
		{
			cin>>a>>b;
			tmn.r=a;
			tmn.c=b;
			v.push_back(tmn);
		}
		a=v[n/2].r;
		b=v[n/2].c;
		s=o=0;
		
		for(i=0;i<n;i++)
		{
			m = (a - v[i].r) * (b - v[i].c);
			if(m > 0)
				s++;
			else if(m < 0)
				o++;
		}
		cout<<s<<" "<<o<<endl;
	}
	return 0;
}

[brianfry713]

Use long long instead of int.

[anacharsis]

What in the problem statement allows us to assume that the lines are drawn through the middle point of the input sequence?