109 - SCUD Busters

[Diskerr]

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?

[Diskerr]

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?

[xbeanx]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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

[xbeanx]

Thanks! I'll check that out.

Wouldn't that give me a RTE though?

[Almost Human]

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]

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 ;
}