10173 - Smallest Bounding Rectangle

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

Post by kenneth »

Hi

Would you have more input / output since I matched all of your testing data but still got WA!

Help is greatly appreciated.

Kenneth

xintactox
New poster
Posts: 14
Joined: Thu Dec 01, 2005 3:17 pm
Location: Brazil

10173 - Smallest Bounding Rectangle

Post by xintactox »

Well, my program works fine for the tests given in the program, but i'm getting WA...
The idea I used is simple: sort the numbers using the x-coordinate as the sorting parameter... The difference between the last point x coordinate and the first point x coordinate should be the base of the rectangle.
Then sort the points using the y coordinate as the parameter. The difference between the last point y coordinate and the first point y coordinate should be the height of the rectangle.
Area = Base * Height

Code: Select all

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

using namespace std;

class point
{
	public:
		double x, y;
};

bool tosortby_x(const point p1, const point p2)
{
	return(p1.x > p2.x);
}

bool tosortby_y(const point p1, const point p2)
{
	return(p1.y > p2.y);
}

int main()
{
	int n;
	double A, B, H;
	vector<point> points;
	point aux;
	while(true)
	{
		cin>>n;
		if(n == 0) break;
		points.clear();
		for(int i = 0; i < n; i++)
		{
			cin>>aux.x>>aux.y;
			points.push_back(aux);
		}
		sort(points.begin(), points.end(), tosortby_x);
		B = fabs(points[0].x - points[points.size()-1].x);
		sort(points.begin(), points.end(), tosortby_y);
		H = fabs(points[0].y - points[points.size()-1].y);
		A = B*H;
		printf("%.3f\n", A);
	}
	return 0;
}
Is it ok?!

Why my problem is getting WA? I just can't find the bug! Please help!
Thanks!

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Hi,

The smallest bounding box could be rotated on an angle.

maurizzzio
New poster
Posts: 5
Joined: Wed Jul 20, 2011 9:02 pm

Re: 10173 - Smallest Bounding Rectangle

Post by maurizzzio »

HINT: for all people trying to solve this problem, read about rotating callipers and an algorithm for the minimum area rectangle enclosing a convex polygon.
link: http://www.cs.purdue.edu/research/techn ... 83-463.pdf

Post Reply

Return to “Volume 101 (10100-10199)”