## 609 - Metal Cutting

Moderator: Board moderators

bjacoke001
New poster
Posts: 6
Joined: Fri Jul 26, 2002 6:42 pm

### 609 - Metal Cutting

I'm getting WA, but I'm fairly confident my algorithm is right. Does anyone have test data which might help to detect problems in my program?

lobow
New poster
Posts: 10
Joined: Tue Jun 08, 2004 7:27 pm
Location: Pelotas - RS - Brazil
Contact:
Hi! Im having problems to discover the points of the equilateral triangle. Someone can help me with how can I draw this triangle?

Tks

lobow
New poster
Posts: 10
Joined: Tue Jun 08, 2004 7:27 pm
Location: Pelotas - RS - Brazil
Contact:
sry, wrong problem

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA
The brute force O(n!) approach gets TLE.
There are more than 10 people who got AC in <=0.010 sec.
I do want to know the algo.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 609 - Metal Cutting

Test data generator.

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

const double EPSILON = 1e-7;

struct point
{
double x, y;
point(double x = 0, double y = 0): x(x), y(y) {}
bool operator<(const point & p) const
{
if (fabs(y - p.y) > EPSILON)
return y < p.y;
return x < p.x;
}

bool operator==(const point & p)const
{
return fabs(x - p.x) <= EPSILON && fabs(y - p.y) <= EPSILON;
}
} ps[1024];

typedef vector < point > polygon;

double cp(point & a, point & b, point & c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool ccw(point & a, point & b, point & c)
{
return cp(a, b, c) > EPSILON;
}

bool ccwOrCollinear(point & a, point & b, point & c)
{
double cp1 = cp(a, b, c);
return cp1 > EPSILON || fabs(cp1) <= EPSILON;
}

// Any three vertex not collinear.
polygon andrewConvexHull(polygon & pg)
{
polygon ch;

sort(pg.begin(), pg.end());
for (int i = 0; i < pg.size(); i++)
{
while (ch.size() >= 2 && ccwOrCollinear(ch[ch.size() - 2], ch[ch.size() - 1], pg[i]))
ch.pop_back();
ch.push_back(pg[i]);
}
for (int i = pg.size() - 1, upper = ch.size() + 1; i >= 0; i--)
{
while (ch.size() >= upper && ccwOrCollinear(ch[ch.size() - 2], ch[ch.size() - 1], pg[i]))
ch.pop_back();
ch.push_back(pg[i]);
}
ch.pop_back();

return ch;
}

int main(int argc, char *argv[])
{
cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

srand(time(NULL));

int cases = 100;
cout << cases << '\n';
for (int cs = 1; cs <= cases;)
{
cout << '\n';
int n = rand() % 400 + 100;
int m = rand() % 400 + 100;
cout << n << ' ' << m << '\n';
int p = rand() % 6 + 3;
polygon pg;
for (int i = 0; i < 1000; i++)
{
int x = rand() % (n - 1) + 1;
int y = rand() % (m - 1) + 1;
pg.push_back(point(x, y));
}
polygon ch = andrewConvexHull(pg);
if (ch.size() < p)
continue;
cout << p << '\n';
for (int j = 0; j < p && j < ch.size(); j++)
cout << ch[j].x << ' ' << ch[j].y << '\n';
cs++;
}

return 0;
}
``````