10173 - Smallest Bounding Rectangle

[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]

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]

Hi,

The smallest bounding box could be rotated on an angle.

[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