OJ Board

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>


typedef struct Point
{
	int x;
	int y;
}TPoint;

typedef struct K
{
	int dest;
	int n;
	int h;
	TPoint *cords;
	TPoint *hull;
}TK;

double findAngle(int i, TPoint* data, int minx, int miny)
{
	double ret = 0;
	int xdif;

	xdif = (data[i].x - minx);

	if (xdif == 0)
	{
		if (data[i].y == miny)
		{
			ret = -1;
		}
		else
		{
			ret = 1000;
		}
	}
	else
	{
		ret = ((double)(data[i].y - miny)/xdif);
		if (ret < 0)
		{
			ret*=-1;
			ret = 2000 - ret;
		}
	}
	return ret;
}

void sortByAngle2(TPoint *data, int l, int r, int minx, int miny)
{
	int i,j;
	TPoint swap;

		if (data[l].x == data[l+1].x)
		{
			for (i=l; i<r; i++)
			{
				for (j=i+1; j<=r; j++)
				{	
					if (data[i].y>data[j].y)
					{
						swap = data[i];
						data[i] = data[j];
						data[j] = swap;
					}
				}	
			}
			
		}
		else if (data[l].y == data[l+1].y)
		{
			for (i=l; i<r; i++)
			{
				for (j=i+1; j<=r; j++)
				{	
					if (data[i].x>data[j].x)
					{
						swap = data[i];
						data[i] = data[j];
						data[j] = swap;
					}
				}	
			}
		}
		else
		{
			for (i=l; i<r; i++)
			{
				for (j=i+1; j<=r; j++)
				{
					if ((double)sqrt((data[i].x-minx)*(data[i].x-minx)+(data[i].y-miny)*(data[i].y-miny)) > (double)sqrt((data[j].x-minx)*(data[j].x-minx)+(data[j].y-miny)*(data[j].y-miny)))
					{
						swap = data[i];
						data[i] = data[j];
						data[j] = swap;
					}
				}
			}
		}
}

void sortByAngle(int lo, int hi, TPoint* data, int minx, int miny)
{
	int left, right, pivI;
	TPoint swap;
	double pivot;

	left = lo;
	right = hi;

	pivI = (left+right)/2;
	pivot = findAngle(pivI, data, minx, miny);

	while (left<=right)
	{
		while ((findAngle(left, data, minx, miny) < pivot) && (left<hi)) left++;
		while ((findAngle(right, data, minx, miny) > pivot) && (right>lo)) right--;

		if (left<=right)
		{
			swap = data[left];
			data[left] = data[right];
			data[right] = swap;
			left++;
			right--;
		}
	}
	if (left>lo) sortByAngle(lo, right, data, minx, miny);
	if (right<hi) sortByAngle(left, hi, data, minx, miny);
}

double crossProduct(TPoint *p1, TPoint *p2, TPoint *p3)
{
	double ret = 0;

	ret = (p2->x - p1->x) * (p3->y - p1->y) - (p3->x - p1->x) * (p2->y - p1->y);

	return ret;
}

void findHull(TK* K, int sort)
{
	int minx, miny;
	int i, j, k;
	int top;

	minx = 5000; /* INF */
	miny = 5000; /* INF */

	for (i=0; i<K->n; i++)
	{
		if (K->cords[i].y < miny)
		{
			minx = K->cords[i].x;
			miny = K->cords[i].y;
		}
		else if (K->cords[i].y == miny)
		{
			if (K->cords[i].x < minx)
			{
				minx = K->cords[i].x;
				miny = K->cords[i].y;
			}
		}
	}
	
	if (sort)
	{
		sortByAngle(0, K->n-1, K->cords, minx, miny);
	}

	i = 0;
	while (i<K->n-1)
	{
		j = i;
		k = j;
		while (j<K->n-1 && findAngle(j, K->cords, minx, miny) == findAngle(j+1, K->cords, minx, miny))
		{
			j++;
		}
		sortByAngle2(K->cords, k, j, minx, miny);
		i = j+1;
	}
	

	K->cords[K->n] = K->cords[0];
	K->hull[0] = K->cords[0];
	K->hull[1] = K->cords[1];
	top = 1;
	for (i=2; i<=K->n; i++)
	{
		while ((crossProduct(&(K->hull[top-1]), &(K->hull[top]), &(K->cords[i])) <= 0) && (top>=1))
		{
			top--;
		}
		top++;
		K->hull[top] = K->cords[i];
	}

	K->h = top+1;
}

int main()
{
	int n, nk, i, j, b;
	int missX, missY;
	double total, temp;
	TPoint missle;
	TK K[21];
	/*freopen("data.in", "r", stdin);
	freopen("data.out", "w", stdout);*/

	nk = 0;
	scanf("%d", &n);

	while (n != -1)
	{
		K[nk].n = n;
		K[nk].h = 0;
		K[nk].dest = 0;
		K[nk].cords = (TPoint*)malloc((n+5)*sizeof(TPoint));
		K[nk].hull = (TPoint*)malloc((n+5)*sizeof(TPoint));

		for (i=0; i<n; i++)
		{
			scanf("%d %d", &(K[nk].cords[i].x), &(K[nk].cords[i].y));
		}
		
		findHull(&(K[nk]), 1);

		nk++;
		scanf("%d", &n);
	}

	K[20].cords = (TPoint*)malloc(105*sizeof(TPoint));
	K[20].hull = (TPoint*)malloc(105*sizeof(TPoint));

	while (scanf("%d %d", &missX, &missY) == 2)
	{
		b = 0;
		for (i=0; i<nk && !b; i++)
		{
			if (K[i].dest == 0)
			{
				K[20].n = K[i].n+1;
				for (j=0; j<K[i].n; j++)
				{
					K[20].cords[j] = K[i].cords[j];
				}
				missle.x = missX;
				missle.y = missY;
				K[20].cords[j] = missle;

				findHull(&(K[20]),1);

				b = 1;
				if (K[i].h != K[20].h)
				{
					b = 0;
				}
				else if (K[i].h == K[20].h)
				{
					for (j=0; j<K[i].h; j++)
					{
						if ((K[i].hull[j].x != K[20].hull[j].x) || (K[i].hull[j].y != K[20].hull[j].y))
						{
							b = 0;
						}
					}
				}

				if (b)
				{
					K[i].dest = 1;
				}
			}
		}
	}

	total = 0.0;
	
	for (i=0; i<nk; i++)
	{
		if (K[i].dest == 1)
		{
			temp = 0.0;
			for (j=1; j<K[i].h; j++)
			{
				temp += (K[i].hull[j-1].x * K[i].hull[j].y) - (K[i].hull[j].x * K[i].hull[j-1].y);
			}

			temp/=2;
			if (temp<0)
			{
				temp*=-1;
			}
			total+=temp;
		}
	}

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

	return 0;
}

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

/** Problem 109: Scud busters */
public class Main {

	private final int DEBUG = 4;
	private final int INFO  = 2;
	private final int NOTHING = 0;
	private int DEBUG_LEVEL = NOTHING;
	
	class Reader {

		BufferedReader stdin;
		
		public Reader () {
			stdin = new BufferedReader (new InputStreamReader(System.in));
		}

		public String readLine () {
			try {
				return stdin.readLine();
			} catch (IOException e) {
				e.printStackTrace();
				return null;
			}
		}
	}
	
	class Point {
		int x, y;
		public Point (int x, int y) {this.x = x; this.y = y;}
		public String toString () {return "{"+x+","+y+"}";}
	}

	ArrayList<ArrayList<Point>> kingdoms;
	ArrayList<Point> missiles;
	ArrayList<ArrayList<Point>> convexHulls;
	
	private double norm (double dx, double dy) {
		return Math.sqrt(
			   Math.pow(dx, 2.0d) 
			 + Math.pow(dy, 2.0d) );
	}
	
	private double angle (double dx, double dy) {
		double norm = norm(dx,dy);
		double angle = Math.acos(dx / norm);
		
		// correction of dy < 0 (cos value the same)
		// to have 0 <= angle < 2*PI
		if (dy < 0)
			angle = 2 * Math.PI - angle;
		
		return angle;
	}
	
	private ArrayList<Point> convexHull (ArrayList<Point> pointSet) {
		/* every point is in the interval [(0,0),(500,500)] */ 
		
		/* get two points: 
		   - p1: get the point with the max x coordinate
		         if more than one, get the one with the smallest y coordinate
		   - p2: get the point with the min x coordinate
		         if more than one, get the one with the greatest y coordinate */
		Point p1 = new Point (-1,501);
		Point p2 = new Point (501, -1);
		for (Point p: pointSet) {
			/* p1 */
			// has p a greater x?
			if (p1.x < p.x)
				p1 = p;
			// if equal x, look at y
			else if (p1.x == p.x) {
				// has p a smaller y?
				if (p1.y > p.y)
					p1 = p;
			}
			
			/* p2 */
			// has p a smaller x?
			if (p.x < p2.x)
				p2 = p;
			// if equal x, look at y
			else if (p2.x == p.x) {
				// has p a larger y?
				if (p.y > p2.y)
					p2 = p;
			}
		}

		Point pivot = p1;
		ArrayList<Point> hull = new ArrayList<Point> ();
		hull.add(pivot);
		// angle to the pivot from the point (-1,-1), 
		// which is out of the area
		double pivotAngle = angle (pivot.x+1, pivot.y+1);

		if (DEBUG_LEVEL == DEBUG)
			System.out.println("Pivot: " + pivot.toString());
		
		// iterate until the break condition is met
		boolean firstHalf = true;
		while (true) {
			
			// one step of the convex hull:
			// calculate the angle of all other points wrt the pivot
			Point minPoint = new Point (0,0);
			double minAngle = 3*Math.PI;
			for (Point p: pointSet) {
				// skip this point if same than pivot
				if (p.equals(pivot))
					continue;
				
				// angle between pivot and new point
				double dx = (double)p.x - pivot.x;
				double dy = (double)p.y - pivot.y;
				double angle = angle (dx, dy);
				
				if (firstHalf) {
					angle = angle - pivotAngle;
				} else {
					// if we are on the second half, we have to correct the angle
					// so that the origin is rotated by 180 deg or PI
					angle = angle - Math.PI;
					
					// and substract the pivot angle
					angle = angle - pivotAngle;
					
					// make sure that the angle is >= 0
					if (angle < 0.0)
						angle = angle + 2*Math.PI;
				}
				
				if (DEBUG_LEVEL == DEBUG)
					System.out.println("Point " + p.toString() + " angle: " + angle);
				
				// do we have a min angle?
				if (angle < minAngle) {
					minPoint = p;
					minAngle = angle;
				}
				// do we have the same min angle?
				// take the point with the larger norm from the pivot
				if (angle == minAngle) {
					double minNorm = norm((double)minPoint.x - pivot.x, (double)minPoint.y - pivot.y);
					double norm = norm (dx, dy);
					if (minNorm < norm) {
						minPoint = p;
					}
				}
			}
			
			/* break condition: the new minPoint is the first one */
			if (minPoint.equals(hull.get(0))) {
				// enter it in the convex hull, so the first and last are the same
				hull.add(minPoint);
				// finish
				break;
			}
			
			/* if we are at the extreme left of the graph, record it */
			if (minPoint.equals(p2)) {
				firstHalf = false;
				if (DEBUG_LEVEL == DEBUG)
					System.out.println("*** Extreme left");
			}
			
			/* the next point on the hull is minPoint */
			hull.add(minPoint);
			pivot = minPoint;
			// angle to the pivot from the point (-1,-1), 
			// which is out of the area
			pivotAngle = angle (pivot.x+1, pivot.y+1);
			
			if (DEBUG_LEVEL == DEBUG)
				System.out.println("Pivot: " + pivot.toString());
		
		}
		
		return hull;
		
	}
	
	private double area (ArrayList<Point> pointSet) {
		double area = 0;
		for (int i = 0; i < pointSet.size() - 1; i++) {
			area += determinant (pointSet.get(i), pointSet.get(i+1));
		}
		return area/2;
	}
	
	private int determinant (Point vect1, Point vect2) {
		return vect1.x*vect2.y - vect1.y*vect2.x;
	}
	
	private boolean inside (ArrayList<Point> pointSet, Point point) {
		// for each vector of the hull, in the counter clockwise direction
		for (int i = 0; i < pointSet.size() - 1; i++) {
			Point vect1 = new Point(pointSet.get(i+1).x - pointSet.get(i).x, pointSet.get(i+1).y - pointSet.get(i).y);
			Point vect2 = new Point(point.x - pointSet.get(i).x, point.y - pointSet.get(i).y);
			
			/* the = 0 here, is for the case, where the point is on the edge */
			if (determinant (vect1, vect2) <= 0)
				return false;
		}
		
		// all determinant are > 0, the point is inside
		return true;
	}
	
	public void run () {
		kingdoms = new ArrayList<ArrayList<Point>> ();
		Reader r = new Reader ();
		
		// read kingdom data
		String line = r.readLine();
		while (!line.trim().equals("-1")) {
			int n = Integer.parseInt(line.trim());
			ArrayList<Point> kingdom = new ArrayList<Point> ();
			kingdoms.add(kingdom);
			for (int i = 0; i<n; i++) {
				line = r.readLine();
				String[] a = line.split("[ ]+");
				kingdom.add(new Point (Integer.parseInt(a[0]), Integer.parseInt(a[1])));
			}
			line = r.readLine();
		}
		
		/* line == "-1" */
		
		// read missiles data
		missiles = new ArrayList<Point> ();
		line = r.readLine();
		while (line != null && line.trim().length() > 0) {
			String[] a = line.trim().split("[ ]+");
			missiles.add(new Point (Integer.parseInt(a[0]), Integer.parseInt(a[1])));
			line = r.readLine();
		}

		// calculate the convex hull
		convexHulls = new ArrayList<ArrayList<Point>> ();
		for (ArrayList<Point> kingdom: kingdoms) {
			ArrayList<Point> hull = convexHull (kingdom);
			convexHulls.add(hull);
			if (DEBUG_LEVEL == INFO) {
				System.out.println("Kingdom: " + kingdom.toString());
				System.out.println("Hull:    " + hull.toString());
			}
		}
		
		// for each missile
		HashMap<String, Boolean> seen = new HashMap<String, Boolean> ();
		double totArea = 0.0;
		for (Point missile: missiles) {
			// for each kingdom, check if the missile is inside that kingdom
			for (ArrayList<Point> hull: convexHulls) {
				if (inside(hull, missile) && seen.get(hull.toString()) == null) {
					totArea += area(hull);
					seen.put(hull.toString(), true);
					
					if (DEBUG_LEVEL == INFO) {
						System.out.println("Point "+ missile + " inside hull: " + hull.toString());
						System.out.println("Area is: " + area(hull));
					}
				}
			}
		}
		System.out.printf ("%.2f\n", totArea);
		
	}
	
	public static void main (String[] args) {
		Main p = new Main ();
		p.run();
	}

}

Code: Select all

import java.io.*;
import java.util.*;
import java.text.*;

class Main {

	@SuppressWarnings("unchecked") 
	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		Vector[] tab = new Vector[20];
		for(int b = 0; b < 20; ++b) tab[b] = new Vector<Point>();

		Vector<Point> bombs = new Vector<Point>();

		int i = -1;
		int counter = 0;

		while(true) {
			line = in.readLine();
            if (line == null) break;
            if (line.equals(null)) break;
            if (line.equals("")) break;

			String[] t = line.trim().split(" ");

			if(t.length == 1 && !t[0].equals("-1")) { i = i + 1; counter++; }

			if(t.length == 2 && i >= 0) {
				Point a = new Point();
				a.x = Integer.parseInt(t[0]);
				a.y = Integer.parseInt(t[1]);
				tab[i].add(a);
			}

			if(t.length == 2 && i < 0) {
			    Point b = new Point();
				b.x = Integer.parseInt(t[0]);
				b.y = Integer.parseInt(t[1]);
				bombs.add(b);
			}

			if(t.length == 1 && t[0].equals("-1")) i = -1;
		}

		double area = 0;

		for(int k = 0; k < 20; ++k) {
			sort(tab[k]);
			Vector<Point> q = graham(tab[k]);
			for(int l = 0; l < bombs.size(); ++l) {
				if(hits(graham(tab[k]), bombs.get(l))) {
					area = area + Math.abs(area(graham(tab[k])));
					break;
				}
			}
		}
		System.out.printf ("%.2f\n", area);
	}

	public static double area(Vector<Point> points) {
		if(points.size() < 3) return 0;
		points.add(points.get(0));

		double a = 0;
		for(int i = 1; i < points.size(); ++i) {
			a += ((points.get(i-1).x * points.get(i).y) - (points.get(i).x * points.get(i-1).y));
		}
		return (a * 0.5);
	}

	public static Vector<Point> graham(Vector<Point> points) {
		if(points.size() < 3) return points;

		int n = points.size();

		Vector<Point> s = new Vector<Point>();
		Vector<Point> tmp = new Vector<Point>();
		s.add(points.get(n - 1));
		s.add(points.get(0));
		s.add(points.get(1));

		for(int i = 2; i < n - 1; ++i) {
			int m = s.size() - 1;

			tmp.add(points.get(i));
			tmp.add(s.get(m - 1));
			tmp.add(s.get(m));

			while(area(tmp) < 0) {
				tmp.removeAllElements();
				s.removeElementAt(s.size() - 1);

				tmp.add(points.get(i));
				tmp.add(s.get(s.size() - 2));
				tmp.add(s.get(s.size() - 1));
			}
			s.add(points.get(i));
			tmp.removeAllElements();
		}

		return s;
	}

	public static boolean hits(Vector<Point> points, Point t) {
		double p = area(points);
		Vector<Point> s = points;

		for(Point xx : s) {
			if(xx.x == t.x && xx.y == t.y) return true;
		}

		s.add(t);
		sort(s);
		Vector<Point> f = graham(s);

		double q = area(f);

		if(p == q) return true;
		else return false;
	}

	public static void first(Vector<Point> points) {
		if(points.size() == 0) return;
		Point a = points.get(0);
		int c = 0;
		for(int i = 1; i < points.size(); ++i) {
			if(a.y > points.get(i).y) { a = points.get(i); c = i; }
			else continue;
		}
		points.remove(c);
		points.add(a);
	}

	public static void sort(Vector<Point> points) {
		if(points.size() == 0) return;
		int n = points.size();
		first(points);

		Point a = points.get(n-1);
		for(int i = 0; i < (n-1); ++i) kot(points.get(n-1), points.get(i));

		bisection(points, 0, n - 2);
	}

	public static int scrumble(Vector<Point> a, int i, int j) {
		double p = a.get(i).alpha;
		int k = i + 1;

		while(k < j) {
			while (k < j && a.get(k).alpha < p)  ++k;
			while (k < j && a.get(j).alpha  >= p) --j;

	        if(k < j) {
		        Point t = a.get(k);
		        a.set(k, a.get(j));
		        a.set(j, t);
			}
		}

   		if(a.get(j).alpha < p) {
    	   	Point u = a.get(i);
    	   	a.set(i, a.get(j));
    	   	a.set(j, u);
     		return(j);
    	 }

    	else {
    	    Point r = a.get(i);
    	    a.set(i, a.get(j-1));
    	    a.set(j-1, r);
      		return(j - 1);
		}
	}

    public static void bisection(Vector<Point> a, int i, int j) {
        if (j - i >= 1) {
			int k = scrumble(a, i, j);
	        bisection(a, i, k - 1);
	        bisection(a, k + 1, j);
		}
	}

	public static void kot(Point a, Point b) {

		double pi = Math.PI;

		if(a.x == b.x) { b.alpha = 90; return; }
		if(a.y == b.y && a.x <= b.x) { b.alpha = 0; return; }
	    if(a.y == b.y && a.x > b.x) { b.alpha = 180; return; }

		double alpha = (Math.atan(((double)(a.y - b.y))/((double)(a.x - b.x)))) * (180 / pi);

		if(a.y != b.y && a.x > b.x) { b.alpha = 180 + alpha; return; }
		if(a.y != b.y &&  a.x < b.x) { b.alpha = alpha; return; }
		else return;
	}
}

class Point {
	public int x;
	public int y;
	public double alpha = 0;

	public Point() {}

	public Point(int a, int b) {
		this.x = a;
		this.y = b;
	}
	public String toString() {
		return ("(" + this.x + ", " + this.y + ")");
	}
}

Code: Select all

deleted as i figured out the problem