109 - SCUD Busters

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

Moderator: Board moderators

Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

Prob 109 need some help..

Post by Diskerr » Thu May 01, 2003 5:44 pm

I have tried to solve prob 109 several times, but I always get WA.

this is my source code :

[cpp]

Code: Select all

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>

using namespace std;

struct Point {
	int x;
	int y;
};

struct Kingdom {
	int N;
	Point p[100];
	vector<int> CH;
	bool Destroyed;
};

bool hit(Kingdom K, Point P);
double calcArea(Kingdom K);
vector<int> makeConvexHull(Point* p, int N);
int direction (Point x, Point y, Point z);

int main()
{
	int N, TK = 0; 
	double Area = 0;
	Point* p;
	Kingdom K[20];

	cin >> N;
	while (N != -1) {
		K[TK].N = N;
		for (int i = 0; i < N; i++) {
			cin >> K[TK].p[i].x >> K[TK].p[i].y;
		}

		K[TK].CH = makeConvexHull(K[TK].p, N);

		K[TK].Destroyed = false;

		cin >> N;
		TK++;
	}

	Point M;	
	while ((cin >> M.x >> M.y)) {
		for (int i = 0; i < TK; i++) {
			if (!K[i].Destroyed && hit(K[i], M)) {
				Area += calcArea(K[i]);
				K[i].Destroyed = true;
			}
		}
	}

	cout << setiosflags(ios::fixed) << setprecision(2) << Area << endl;
}

bool hit(Kingdom K, Point P)
{
	int OldDirection = 0, NewDirection;
	for (int i = 0; i < K.CH.size() - 1; i++) {
		NewDirection = direction(K.p[K.CH[i]], K.p[K.CH[i + 1]], P);

		if (NewDirection == 0)
			continue; 	

		if (OldDirection == 0)
			OldDirection = NewDirection;
	
		if (OldDirection != NewDirection)
			return false;
	}

	return true;
}

double calcArea(Kingdom K)
{
	double Result = 0;
	for (int i = 1; i < K.CH.size() - 1; i++) {
		Result += abs(K.p[K.CH[0]].x * K.p[K.CH[i]].y
					+ K.p[K.CH[i]].x * K.p[K.CH[i + 1]].y 
					+ K.p[K.CH[i + 1]].x * K.p[K.CH[0]].y
					- K.p[K.CH[i]].x * K.p[K.CH[0]].y
					- K.p[K.CH[i + 1]].x * K.p[K.CH[i]].y
					- K.p[K.CH[0]].x * K.p[K.CH[i + 1]].y);
	}

	return (Result / 2);
}

vector<int> makeConvexHull(Point* p, int N)
{
	int         ld, nd, lp;
	vector<int> r;
	
	lp = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (lp == j) continue;

			ld = 0;
			for (int k = 0; k < N; k++) {
				nd = direction(p[i], p[j], p[k]);

				if (ld == 0) 
					ld = nd;
				else if (nd != 0 && nd != ld)
					break;
			}

			if (ld != 0 && (ld == nd || nd == 0)) {
				r.push_back(i);
				lp = i;
				i = j - 1;
				break; 
			}
		}

		if (r.size() > 1 && r[0] == r[r.size() - 1])
			break;
	}
	
	return r;
}

int direction(Point x, Point y, Point z)
{
	int t = x.x * y.y + y.x * z.y + z.x * x.y
		- x.y * y.x - y.y * z.x - z.y * x.x;

	if (t > 0)
		return 1;
	else if (t < 0)
		return -1;
	else
		return 0;
}
[/cpp]

I heard that there are no test case which missile lands wall of convex.
(So each AC prog makes different answers)

Why my code get WA from judge?
Sorry for my poor English.

Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

Prob 109 need some help..

Post by Diskerr » Thu May 01, 2003 5:46 pm

I have tried to solve prob 109 several times, but I always get WA.

this is my source code :

[cpp]

Code: Select all

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>

using namespace std;

struct Point {
	int x;
	int y;
};

struct Kingdom {
	int N;
	Point p[100];
	vector<int> CH;
	bool Destroyed;
};

bool hit(Kingdom K, Point P);
double calcArea(Kingdom K);
vector<int> makeConvexHull(Point* p, int N);
int direction (Point x, Point y, Point z);

int main()
{
	int N, TK = 0; 
	double Area = 0;
	Point* p;
	Kingdom K[20];

	cin >> N;
	while (N != -1) {
		K[TK].N = N;
		for (int i = 0; i < N; i++) {
			cin >> K[TK].p[i].x >> K[TK].p[i].y;
		}

		K[TK].CH = makeConvexHull(K[TK].p, N);

		K[TK].Destroyed = false;

		cin >> N;
		TK++;
	}

	Point M;	
	while ((cin >> M.x >> M.y)) {
		for (int i = 0; i < TK; i++) {
			if (!K[i].Destroyed && hit(K[i], M)) {
				Area += calcArea(K[i]);
				K[i].Destroyed = true;
			}
		}
	}

	cout << setiosflags(ios::fixed) << setprecision(2) << Area << endl;
}

bool hit(Kingdom K, Point P)
{
	int OldDirection = 0, NewDirection;
	for (int i = 0; i < K.CH.size() - 1; i++) {
		NewDirection = direction(K.p[K.CH[i]], K.p[K.CH[i + 1]], P);

		if (NewDirection == 0)
			continue; 	

		if (OldDirection == 0)
			OldDirection = NewDirection;
	
		if (OldDirection != NewDirection)
			return false;
	}

	return true;
}

double calcArea(Kingdom K)
{
	double Result = 0;
	for (int i = 1; i < K.CH.size() - 1; i++) {
		Result += abs(K.p[K.CH[0]].x * K.p[K.CH[i]].y
					+ K.p[K.CH[i]].x * K.p[K.CH[i + 1]].y 
					+ K.p[K.CH[i + 1]].x * K.p[K.CH[0]].y
					- K.p[K.CH[i]].x * K.p[K.CH[0]].y
					- K.p[K.CH[i + 1]].x * K.p[K.CH[i]].y
					- K.p[K.CH[0]].x * K.p[K.CH[i + 1]].y);
	}

	return (Result / 2);
}

vector<int> makeConvexHull(Point* p, int N)
{
	int         ld, nd, lp;
	vector<int> r;
	
	lp = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (lp == j) continue;

			ld = 0;
			for (int k = 0; k < N; k++) {
				nd = direction(p[i], p[j], p[k]);

				if (ld == 0) 
					ld = nd;
				else if (nd != 0 && nd != ld)
					break;
			}

			if (ld != 0 && (ld == nd || nd == 0)) {
				r.push_back(i);
				lp = i;
				i = j - 1;
				break; 
			}
		}

		if (r.size() > 1 && r[0] == r[r.size() - 1])
			break;
	}
	
	return r;
}

int direction(Point x, Point y, Point z)
{
	int t = x.x * y.y + y.x * z.y + z.x * x.y
		- x.y * y.x - y.y * z.x - z.y * x.x;

	if (t > 0)
		return 1;
	else if (t < 0)
		return -1;
	else
		return 0;
}
[/cpp]

I heard that there are no test case which missile lands wall of convex.
(So each AC prog makes different answers)

Why my code get WA from judge?
Sorry for my poor English.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Problem 109 - SCUD Busters (need boundary cases)

Post by xbeanx » Fri Aug 08, 2003 4:17 pm

Hey guys. I'm having a lot of trouble with problem 109 (scud busters).

I have an AC version of it written in C++, but unfortunately, the logic it follows is nothing like mine. However, my program and the AC program matches exactly on every sample input I could find.

I have tested cases where the missiles land on the corner of a kingdom, cases where the missiles land on the kingdom wall, cases where missiles land within 0.001 units inside/outside the wall.

Argh...!!! Would someone be able to take a quick look at my (sloppy) code and tell me where my problem is???

Thanks!!

PS. Since gcj sucks, I had to build my own Stack and NumberFormatter, that's why there's a lot of code. Also, I know my sorting routine sucks, but it works in less than a second so it suffices.

[java]
import java.io.IOException;
import java.util.StringTokenizer;

class Main {
static Polygon[] kingdoms = new Polygon[20];

public static void main(String[] args) throws IOException {
int nhouses, nkingdoms = 0;
// read in points, get CH, add to array
while((nhouses = Integer.parseInt(readLine(16))) != -1) {
Point[] houses = new Point[nhouses];

for(int i = 0; i < nhouses; i++) {
StringTokenizer st = new StringTokenizer(readLine(16));
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
Point point = new Point(x, y);
houses = point;
}

Polygon polygon = Polygon.convexHull(houses, nhouses);
kingdoms[nkingdoms++] = polygon;
}
// read in missiles, check for intersection
int pointCount = 0;
String in;
while((in = readLine(16)) != null) {
StringTokenizer st = new StringTokenizer(in);
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
Point p = new Point(x, y);
for(int i = 0; i < nkingdoms; i++)
if(kingdoms.containsPoint(p)) kingdoms.destroy();
}
// get total area
double area = 0.0;
for(int i = 0; i < nkingdoms; i++)
if(kingdoms.isBombed()) area += kingdoms.getArea();

System.out.println(truncate(area, 2));
}
// used in place of NumberFormat
static String truncate(double s, int places) {
String ret = new String("0.");
if(s == 0) {
for(int i = 0; i < places; i++) ret += "0";
return ret;
}

ret = Long.toString(Math.round(s * Math.pow(10, places)));
ret = ret.substring(0, ret.length() - places) + "." +
ret.substring(ret.length() - places);

return ret;
}

static String readLine(int maxLg) throws IOException {
byte[] lin = new byte[maxLg];
int lg = 0, car = -1;

while(lg < maxLg) {
car = System.in.read();
if(car<0 || car=='\n') break;
lin[lg++] += car;
}

if(car<0 && lg==0) return null;
return new String(lin, 0, lg).trim();
}
}
// stack used in Graham's Scan
class Stack {
private Object[] s;
private int size, capacity;

public Stack(int capacity) {
s = new Object[capacity];
this.capacity = capacity; this.size = 0;
}

public Object[] toArray() {
Object[] arr = new Object[size];
for(int i = 0; i < size; i++) arr = s;
return arr;
}

public int size() {return size;}
public void push(Object o) {if(size < capacity) s[size++] = o;}
public void pop() {if(size > 0) s[--size] = null;}
public Object top() {return (size-1 >= 0) ? s[size-1] : null;}
public Object nextToTop() {return (size-2 >= 0) ? s[size-2] : null;}

public String toString() {
String str = new String();
for(int i = 0; i < size; i++) str += new String(s + "\n");
return str;
}
}

class Polygon {
private Point[] points;
private int npoints;
private boolean bombed = false;
private double area;

public Polygon(Point[] points, int npoints) {
this.points = points; this.npoints = npoints;
area = calcArea();
}

public void destroy() {bombed = true;}
public boolean isBombed() {return bombed;}
public double getArea() {return area;}

private double calcArea() {
Point[] tmp = new Point[npoints+2];
for(int i = 0; i < npoints; i++) tmp = points;
tmp[npoints] = points[0]; tmp[npoints+1] = points[1];

double area = 0.0;
for(int i=1, j=2, k=0; i<=npoints; i++, j++, k++)
area += (tmp[i].x * (tmp[j].y-tmp[k].y));

return area / 2;
}
// check point in poly using winding
public boolean containsPoint(Point p) {
Point[] tmp = new Point[npoints+1];
for(int i = 0; i < npoints; i++) {
if(points[i].equals(p)) return true;
tmp[i] = points[i];
}
tmp[npoints] = points[0];

int wn = 0;
for(int i = 0; i < npoints; i++) {
if(tmp[i].y <= p.y) {
if(tmp[i+1].y > p.y)
if(isLeft(tmp[i], tmp[i+1], p) > 0) wn++;
} else {
if(tmp[i+1].y <= p.y)
if(isLeft(tmp[i], tmp[i+1], p) < 0) wn--;
}
}

return (wn!=0);
}
// construct CH by Graham's Scan
public static Polygon convexHull(Point[] points, int npoints) {
Point[] sortedPoints = radialSort(points, npoints);

Stack stack = new Stack(npoints);
stack.push(sortedPoints[0]);
stack.push(sortedPoints[1]);
stack.push(sortedPoints[2]);

int i = 3;
while(i < npoints) {
double left = isLeft((Point) stack.nextToTop(),
(Point) stack.top(), sortedPoints[i]);

if(left > 0) stack.push(sortedPoints[i++]);
else stack.pop();
}

int size = stack.size();
Object[] tmp = stack.toArray();
Point[] hull = new Point[size];
for(i = 0; i < size; i++) hull[i] = (Point) tmp[i];

return new Polygon(hull, size);
}
// sort points acc. to polar angle
private static Point[] radialSort(Point[] points, int npoints) {
Point[] sorted = new Point[npoints];
int lowest = 0;
for(int i = 1; i < npoints; i++)
if(points[i].y < points[lowest].y) lowest = i;
else if(points[i].y == points[lowest].y)
if(points[i].x > points[lowest].x) lowest = i;

int count = 0;
sorted[count++] = points[lowest];
points[lowest] = null;

double[] angles = new double[npoints];
for(int i = 0; i < npoints; i++)
if(points[i] != null)
angles[i] = getAngle(sorted[0], points[i]);

boolean done = false;
while(!done) {
done = true;
int smallAngle = 0;
for(int i = 0; i < npoints; i++)
if(points[i] != null) {
smallAngle = i;
done = false;
break;
}

if(done) continue;

for(int i = 0; i < npoints; i++)
if(points[i] != null)
if(angles[i] < angles[smallAngle]) smallAngle = i;

sorted[count++] = points[smallAngle];
points[smallAngle] = null;
}
return sorted;
}

// <0 if right, =0 if on line, >0 if left
private static double isLeft(Point p0, Point p1, Point p2) {
return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}

private static double getAngle(Point p1, Point p2) {
return Math.atan2(p2.y-p1.y, p2.x-p1.x);
}

public String toString() {
String str = new String();
for(int i = 0; i < npoints; i++) str += new String(points[i] + "\n");
str += new String("Area: " + area + "\n");
return str;
}
}

class Point {
public int x, y;

public Point(int x, int y) {
this.x = x; this.y = y;
}

public boolean equals(Point p) {return x==p.x && y==p.y;}

public String toString() {
return new String(x + "," + y);
}
}
[/java]

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Aug 08, 2003 4:28 pm

Well wouldn't ya know it.. I tried using NEGATIVE inputs in my program, and noticed I got a different answer....

hmmmmm...

Does the OJ use negatives?

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Aug 08, 2003 4:50 pm

The online judge does not use negatives. I put a check in my program that would enter an infinite loop if a negative was encountered (thus giving me a TLE). It gave me WA so I know there's no negatives.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Aug 08, 2003 7:53 pm

Please if someone has any more test inputs post them.

I have an AC and my own WA. The outputs match exactly on every input I've tested so far.

Thanks. Greg

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Aug 08, 2003 8:31 pm

Mine also seems to pass all tests. I have an accepted one here and they give the same answer on every test I've tried. :(

If you ever figure out what it is let me know!

G

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Aug 08, 2003 8:42 pm

I may be on to something here......

I put a triple-nested for loop in my program, to see if I would get a TLE...

Code: Select all

for( 0 to 1000000000 )
	for( 0 to 1000000000 )
		for( 0 to 1000000000 )
			;
And ran it on my linux box. I waited about 3 minutes and then stopped it. So I was expecting to get a TLE from the judge but I still got a WA.....

Why? I put the loop at a point BEFORE any output of my program, so the judge has no basis for his judgement...!!!!!!!!!!!!!!!11

Anyone?!?!?

EDIT::: If I put the nested for loops before the line

Polygon polygon = Polygon.convexHull(houses, nhouses);

I get TLE. If I put it right after, I get a WA. I'm thinking this is a weird compiler bug.. ? Also, notice there is no output in the convexhull method.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Aug 08, 2003 9:59 pm

One more thing. Notice the part of my code in convexHull() :

[java]
int i = 3;
while(i < npoints) {
double left = isLeft((Point) stack.nextToTop(),
(Point) stack.top(), sortedPoints);

if(left > 0) stack.push(sortedPoints[i++]);
else stack.pop();
}
[/java]

if I put the FOR loops before this part it TLEs, if I put the FORs after, it gives WA..

Argh!!!!![/java]

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto » Fri Aug 08, 2003 11:39 pm

Hi all,

I got the correct answer for the examples posted in the forum, but I still get WA.
Anyone have a suggestion for a sneaky input?

[cpp]
#include <cstdio>
#include <memory>
#include <cfloat>

// The base types
#ifdef WIN32
typedef __int8 int8;
typedef __int16 int16;
typedef __int32 int32;
typedef __int64 int64;
typedef unsigned __int8 uint8;
typedef unsigned __int16 uint16;
typedef unsigned __int32 uint32;
typedef unsigned __int64 uint64;
#else
typedef char int8;
typedef short int16;
typedef long int32;
typedef long long int int64;
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned long uint32;
typedef unsigned long long int uint64;
#endif

// These macros safely delete (an array of) objects
#define SAFE_DELETE(pObj) { if(pObj) { delete pObj; pObj = NULL; } }
#define SAFE_DELETE_ARRAY(pArr) { if(pArr) { delete[] pArr; pArr = NULL; } }

// A city is defined by its coordinates
typedef struct CITY
{
uint16 u16X; // The x location of the city
uint16 u16Y; // The y location of the city
}LOCATION;

// The kingdom class
class CKingdom
{
private:
bool m_bBombarded; // Has the kingdom been bombarded?
CITY *m_pCities; // The border cities
uint8 m_u8TotCities; // The total amount of border cities

public:
// Function prototypes
CKingdom();
~CKingdom();
void AddCity(const CITY *pCity);
double Area() const;
bool Bombard(const LOCATION *pLoc);
bool DeleteCity(uint8 u8Pos);
bool InsertCity(uint8 u8Pos, const CITY *pCity);
bool IsBombarded() { return m_bBombarded; }
bool IsLocationWithinBorders(const LOCATION *pLoc) const;
bool IsSharpAngle(const CITY *pCityA, const CITY *pCityB, const CITY *pCityC) const;
void PrintPath() const;
};

// Uncomment the following line to show debug info
//#define TEST

// The global variables
CKingdom **g_ppKingdoms; // The kingdoms
uint8 g_u8TotKingdoms; // The total amount of kingdoms


//---------------------------------------------------------------------------
// F U N C T I O N S
//---------------------------------------------------------------------------


// This function is the entrance of the app
int main()
{
double dBombardedArea = 0.0;
int16 i16TotCities;
LOCATION loc;

// Get the specifications of the kingdoms
while(scanf("%hi", &i16TotCities) == 1 && i16TotCities != -1)
{
// Add a new kingdom
CKingdom **ppTemp;
uint8 u8City;

// Augment the amount of kingdoms with 1
ppTemp = new CKingdom*[g_u8TotKingdoms+1];
memcpy(ppTemp, g_ppKingdoms, g_u8TotKingdoms * sizeof(CKingdom *));
SAFE_DELETE_ARRAY(g_ppKingdoms);
g_ppKingdoms = ppTemp;
g_ppKingdoms[g_u8TotKingdoms] = new CKingdom;
g_u8TotKingdoms++;

// Get the cities
for(u8City=0;u8City<i16TotCities;u8City++)
{
CITY city;

// Add the new city
scanf("%hu %hu", &city.u16X, &city.u16Y);
g_ppKingdoms[g_u8TotKingdoms-1]->AddCity(&city);

#ifdef TEST
// Show the new kingdom
printf("(%2u,%2u) -> ", city.u16X, city.u16Y);
g_ppKingdoms[g_u8TotKingdoms-1]->PrintPath();
#endif
}

#ifdef TEST
// Show the area of the kingdom
printf("Area = %f\n\n", g_ppKingdoms[g_u8TotKingdoms-1]->Area());
#endif
}

// Handle the missile attacks
while(scanf("%hu %hu", &loc.u16X, &loc.u16Y) == 2)
{
#ifdef TEST
// Show the missile's location
printf("Missile: (%hu,%hu)\n", loc.u16X, loc.u16Y);
#endif

// Check which kingdoms are hit by the missile
for(uint8 u8Kingdom=0;u8Kingdom<g_u8TotKingdoms;u8Kingdom++)
{
// Has this kingdom not been hit yet?
if(!g_ppKingdoms[u8Kingdom]->IsBombarded())
{
// Bombard the kingdom
g_ppKingdoms[u8Kingdom]->Bombard(&loc);

#ifdef TEST
// Has it been a hit?
if(g_ppKingdoms[u8Kingdom]->IsBombarded())
printf("Kingdom %u has been hit\n", u8Kingdom);
#endif
}
}
}

// Calculate the area of the kingdoms that have been bombarded
for(uint8 u8Kingdom=0;u8Kingdom<g_u8TotKingdoms;u8Kingdom++)
{
// Has the kingdom been bombarded?
if(g_ppKingdoms[u8Kingdom]->IsBombarded())
dBombardedArea += g_ppKingdoms[u8Kingdom]->Area();
}

// Show the total area which has (successfully) been bombarded
#ifdef TEST
printf("Bombarded area = ");
#endif
printf("%.2f\n", dBombardedArea);

// Free the resources
for(uint8 u8=0;u8<g_u8TotKingdoms;u8++) SAFE_DELETE(g_ppKingdoms[u8]);
SAFE_DELETE_ARRAY(g_ppKingdoms);

return 0;
}


//---------------------------------------------------------------------------


// The constructor
CKingdom::CKingdom()
{
// Initialize the class variables
m_pCities = NULL;
m_u8TotCities = 0;
m_bBombarded = false;
}


//---------------------------------------------------------------------------


// The destructor
CKingdom::~CKingdom()
{
// Free the resources
SAFE_DELETE_ARRAY(m_pCities);
}


//---------------------------------------------------------------------------


// This function adds a new city to the kingdom
void CKingdom::AddCity(const CITY *pCity)
{
// Do we currently have 0 or 1 cities?
if(m_u8TotCities < 2)
{
// Add the city
InsertCity(m_u8TotCities, pCity);
}
// Do we currently have 2 cities?
else if(m_u8TotCities == 2)
{
// Fit the new city in clockwise order
if(IsSharpAngle(&m_pCities[0], pCity, &m_pCities[1])) InsertCity(1, pCity);
else InsertCity(2, pCity);
}
else
{
uint8 u8City;

// Find a fit
for(u8City=0;u8City<m_u8TotCities;u8City++)
{
// Does the new city fit between this city and the next?
if(IsSharpAngle(&m_pCities[u8City], pCity, &m_pCities[(u8City+1) % m_u8TotCities])) break;
}

// Did we find a fit?
if(u8City != m_u8TotCities)
{
bool bNonFitting;

// Insert the new city
InsertCity(u8City+1, pCity);

// Prune the non-fitting cities
do
{
// Check all adjoining borders
bNonFitting = false;
for(u8City=0;u8City<m_u8TotCities;u8City++)
{
// Doesn't the middle city fit?
if(!IsSharpAngle(&m_pCities[u8City], &m_pCities[(u8City+1) % m_u8TotCities], &m_pCities[(u8City+2) % m_u8TotCities]))
{
// Remove the city
DeleteCity((u8City+1) % m_u8TotCities);
bNonFitting = true;
break;
}
}
}while(bNonFitting);
}
}
}


//---------------------------------------------------------------------------


// This function calculates the area of the kingdom
double CKingdom::Area() const
{
double dArea = 0.0;

// i=n-1
// area = 0.5 * SUM ( X * Y - X * Y )
// i=0 i i+1 i+1 i

// Go through all vertices
for(uint8 u8City=0;u8City<m_u8TotCities;u8City++)
{
uint8 u8NextCity;

// Calculate the area
u8NextCity = (u8City + 1) % m_u8TotCities;
dArea += m_pCities[u8City].u16X * m_pCities[u8NextCity].u16Y -
m_pCities[u8NextCity].u16X * m_pCities[u8City].u16Y;
}
dArea *= 0.5;

return dArea < 0.0 ? -dArea : dArea;
}


//---------------------------------------------------------------------------


// This function bombards the kingdom
bool CKingdom::Bombard(const LOCATION *pLoc)
{
// Is the location within the borders of the kingdom?
if(IsLocationWithinBorders(pLoc)) m_bBombarded = true;

return m_bBombarded;
}


//---------------------------------------------------------------------------


// This function removes the specified city
bool CKingdom::DeleteCity(uint8 u8Pos)
{
bool bResult = false;

// Do we have a legal position?
if(u8Pos <= m_u8TotCities)
{
// Don't reallocate memory. Simply don't use the last of the allocated cities
if(u8Pos < m_u8TotCities) memcpy(&m_pCities[u8Pos], &m_pCities[u8Pos+1], (m_u8TotCities-u8Pos-1) * sizeof(CITY));
m_u8TotCities--;

bResult = true;
}

return bResult;
}


//---------------------------------------------------------------------------


// This function insert the city at the specified position
bool CKingdom::InsertCity(uint8 u8Pos, const CITY *pCity)
{
bool bResult = false;

// Do we have a legal position?
if(u8Pos <= m_u8TotCities)
{
CITY *pTemp;

// Augment the amount of cities with 1
pTemp = new CITY[m_u8TotCities+1];

// Insert the city
memcpy(pTemp, m_pCities, u8Pos * sizeof(CITY));
memcpy(&pTemp[u8Pos], pCity, sizeof(CITY));
memcpy(&pTemp[u8Pos+1], &m_pCities[u8Pos], (m_u8TotCities-u8Pos) * sizeof(CITY));

// Swap the buffers
SAFE_DELETE_ARRAY(m_pCities);
m_pCities = pTemp;
m_u8TotCities++;

bResult = true;
}

return bResult;
}


//---------------------------------------------------------------------------


// This function determines whether the angle between 2 borders is smaller than 180 degrees
bool CKingdom::IsSharpAngle(const CITY *pCityA, const CITY *pCityB, const CITY *pCityC) const
{
// Is the angle between 0 and 180 degrees?
return (pCityA->u16X - pCityB->u16X) * (pCityC->u16Y - pCityB->u16Y) -
(pCityA->u16Y - pCityB->u16Y) * (pCityC->u16X - pCityB->u16X) > 0;
}


//---------------------------------------------------------------------------


// This function determines whether the specified location falls within the borders of the kingdom
bool CKingdom::IsLocationWithinBorders(const LOCATION *pLoc) const
{
uint8 u8City;

// Check whether the location would fit the polygon
for(u8City=0;u8City<m_u8TotCities;u8City++)
{
// Does the location fit between this city and the next?
if(IsSharpAngle(&m_pCities[u8City], pLoc, &m_pCities[(u8City+1) % m_u8TotCities])) break;
}

return u8City == m_u8TotCities;
}


//---------------------------------------------------------------------------


// This function shows the clockwise border walk
void CKingdom::PrintPath() const
{
// Print the border cities in clockwise order
for(uint8 u8City=0;u8City<m_u8TotCities;u8City++) printf("(%2u,%2u) ", m_pCities[u8City].u16X, m_pCities[u8City].u16Y);
printf("\n");
}
[/cpp]

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto » Sat Aug 09, 2003 12:16 am

Hi all,

Ok, I got accepted. The problem was the calculation of the angle.
To make the source code Accept, change the IsSharpAngle function to:

[cpp]// This function determines whether the angle between 2 borders is smaller than 180 degrees
bool CKingdom::IsSharpAngle(const CITY *pCityA, const CITY *pCityB, const CITY *pCityC) const
{
// Is the angle between 0 and 180 degrees?
return (pCityA->u16X - pCityB->u16X) * (pCityC->u16Y - pCityB->u16Y) -
(pCityA->u16Y - pCityB->u16Y) * (pCityC->u16X - pCityB->u16X) >= 0;
} [/cpp]

I originally had >0 instead of >=0.

ggll
New poster
Posts: 13
Joined: Tue Jun 10, 2003 5:15 am

Post by ggll » Tue Aug 12, 2003 11:59 am

Most likely you got an exception in this part. You can use "try catch" to verify this.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Thu Aug 14, 2003 1:19 pm

Thanks! I'll check that out.

Wouldn't that give me a RTE though?

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

109 - SCUD Buster - WA

Post by Almost Human » Fri Nov 07, 2003 4:47 am

I got WA on this problem and I have tried all input in this forum, and it looked fine.

can anybody post more input, output please ???

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Sat Nov 08, 2003 10:40 am

can somebody check my code ... ???

thank you

Code: Select all

/*SCUD Busters*/
#include <math.h>
#include <stdio.h>

#define maxKingdom 20
#define maxSite 100
#define mathPI ( double ) 3.14159265358979323

struct vertex
{
	int x , y ;
} kingdomVertex[maxKingdom][maxSite+1] , temporary[maxSite+1] , missile ;

int totalKingdomVertex[maxKingdom] ;
int flag[maxKingdom] = { 0 } ;
double degree[maxSite] , temp , area[maxKingdom] ;

int leftTurn ( struct vertex , struct vertex , struct vertex ) ;
int isBombed ( struct vertex* , struct vertex , int ) ;
double calculateArea ( struct vertex* , int ) ;

int main ( void )
{
	int numOfKingdom = 0 , i , j , numOfVertex , max , min ;
	double totalBombed ;

	/*freopen ( "109.in" , "r" , stdin ) ;
	freopen ( "109.out" , "w" , stdout ) ;*/

	while ( scanf ( "%d" , &numOfVertex ) != EOF , numOfVertex != -1 )
	{
		for ( i = max = 0 ; i < numOfVertex ; i ++ )
		{
			scanf ( "%d %d" , &temporary[i].x , &temporary[i].y ) ;

			if ( temporary[i].y > temporary[max].y )
			{
				max = i ;
			}
			else if ( temporary[i].y == temporary[max].y )
			{
				if ( temporary[i].x < temporary[max].x )
				{
					max = i ;
				}
			}
		}

		temporary[0].x ^= temporary[max].x ^= temporary[0].x ^= temporary[max].x ;
		temporary[0].y ^= temporary[max].y ^= temporary[0].y ^= temporary[max].y ;

		/*Calculate elevation*/
		for ( i = 1 ; i < numOfVertex ; i ++ )
		{
			if ( temporary[0].x - temporary[i].x )
			{
				degree[i] = atan ( ( double ) ( temporary[0].y - temporary[i].y ) / ( double ) ( temporary[i].x - temporary[0].x ) ) ;

				if ( degree[i] < 0 )
				{
					degree[i] += mathPI ;
				}
			}
			else
			{
				degree[i] = mathPI / 2 ;
			}
		}

		/*Sorting by elevation ascending*/
		for ( i = 1 ; i < numOfVertex ; i ++ )
		{
			for ( j = i + 1 , min = i ; j < numOfVertex ; j ++ )
			{
				if ( degree[j] < degree[min] )
				{
					min = j ;
				}
			}

			if ( min != i )
			{
				temporary[i].x ^= temporary[min].x ^= temporary[i].x ^= temporary[min].x ;
				temporary[i].y ^= temporary[min].y ^= temporary[i].y ^= temporary[min].y ;
				temp = degree[min] ;
				degree[min] = degree[i] ;
				degree[i] = temp ;
			}
		}

		/*Graham's Scan Algorithm*/
		temporary[numOfVertex++] = temporary[0] ;
		totalKingdomVertex[numOfKingdom] = i = 0 ;
		kingdomVertex[numOfKingdom][totalKingdomVertex[numOfKingdom]++] = temporary[i++] ;
		kingdomVertex[numOfKingdom][totalKingdomVertex[numOfKingdom]++] = temporary[i++] ;
		kingdomVertex[numOfKingdom][totalKingdomVertex[numOfKingdom]++] = temporary[i++] ;

		for ( ; i < numOfVertex ; i ++ )
		{
			while ( !leftTurn ( kingdomVertex[numOfKingdom][totalKingdomVertex[numOfKingdom]-2] , kingdomVertex[numOfKingdom][totalKingdomVertex[numOfKingdom]-1] , temporary[i] ) )
			{
				totalKingdomVertex[numOfKingdom] -- ;
			}

			kingdomVertex[numOfKingdom][totalKingdomVertex[numOfKingdom]++] = temporary[i] ;
		}

		area[numOfKingdom] = calculateArea ( kingdomVertex[numOfKingdom] , totalKingdomVertex[numOfKingdom] ) ;

		numOfKingdom ++ ;
	}

	while ( scanf ( "%d %d" , &missile.x , &missile.y ) != EOF )
	{
		for ( i = 0 ; i < numOfKingdom ; i ++ )
		{
			if ( !flag[i] )
			{
				if ( isBombed ( kingdomVertex[i] , missile , totalKingdomVertex[i] ) )
				{
					flag[i] = 1 ;
				}
			}
		}
	}

	for ( totalBombed = i = 0 ; i < numOfKingdom ; i ++ )
	{
		if ( flag[i] ) totalBombed += area[i] ;
	}

	printf ( "%.2lf\n" , totalBombed ) ;

	return 0 ;
}

int leftTurn ( struct vertex vertex1 , struct vertex vertex2 , struct vertex vertex3 )
{
	return ( ( vertex2.x - vertex1.x ) * ( vertex3.y - vertex1.y ) - ( vertex3.x - vertex1.x ) * ( vertex2.y - vertex1.y ) < 0 ) ;
}

double calculateArea ( struct vertex* polygon , int numOfVertex )
{
	double result ;
	int i ;

	for ( i = 1 , result = 0 ; i < numOfVertex ; i ++ )
	{
		result += ( ( polygon[i-1].x * polygon[i].y ) - ( polygon[i].x * polygon[i-1].y ) ) ;
	}

	return ( - result / 2 ) ;
}

int isBombed ( struct vertex* area , struct vertex bomb , int numOfVertex )
{
	int i ;

	for ( i = 0 ; i < numOfVertex - 1 ; i ++ )
		if ( !leftTurn ( area[i] , area[i+1] , bomb ) ) return 0 ;

	return 1 ;
}

Post Reply

Return to “Volume 1 (100-199)”