1.
package acm_11072_points;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeSet;
/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_11072_points
* Link:
*
* @author Martin Lambeck
* @version 1.0, 31.08.2010
*
* Method : convex hull (graham scan)
* Status : Accepted
* Runtime: 2,484
*/
public class Main
{
//static Scanner sc = new Scanner(System.in);
final static double EPSILON = 0.00001;
static BufferedIntReader sc = new BufferedIntReader();
static ArrayList<Point> frame = new ArrayList<Point>(100000);
static ArrayList<Point> check = new ArrayList<Point>(100000);
static ArrayList<Point> hull = new ArrayList<Point>(100000);
static ArrayList<Point> copy = new ArrayList<Point>(100000);
static BufferedOutputStream out = new BufferedOutputStream(System.out);
public static void main(String... args) throws IOException
{
try
{
while (true)
testcase();
} catch (IllegalStateException e)
{
if (!(e.getCause() instanceof java.io.EOFException))
throw e;
}
out.flush();
}
public static void testcase() throws IOException
{
frame.clear();
check.clear();
hull.clear();
copy.clear();
int p = sc.nextInt();
for (int i = 0; i < p; i++)
frame.add(new Point(sc.nextInt(), sc.nextInt()));
int r = sc.nextInt();
for (int i = 0; i < r; i++)
check.add(new Point(sc.nextInt(), sc.nextInt()));
hull();
check();
for (Point pt : check)
out.write((pt.dismissed ? "outside\n" : "inside\n").getBytes());
}
static void check()
{
TreeSet<Point> ts = new TreeSet<Point>(hull);
Point p0 = hull.get(0);
for (Point p : check)
if ((p.y < p0.y) || ((p.y == p0.y) && (p.x < p0.x)))
p.dismissed = true;
else
p.setAngle(p0);
for (int i = 0; i < check.size(); i++)
{
Point p = check.get(i);
if (!p.dismissed)
{
Point l = ts.floor(p);
Point h = ts.ceiling(p);
if ((l == null) || (h == null) ||
((Math.abs(p.angle - h.angle) < EPSILON) && (p.dist > (h.dist+EPSILON))) ||
((Math.abs(p.angle - l.angle) < EPSILON) && (p.dist > (l.dist+EPSILON))) ||
!p.isLeft(l, h))
{
p.dismissed = true;
}
}
}
}
static void hull()
{
Point p0 = frame.get(0);
//find point with lowest y (and lowest x among them on tie)
for (Point p : frame)
if ((p.y < p0.y) || ((p.y == p0.y) && (p.x < p0.x)))
p0 = p;
//set angle between p0,x-axis,p for any Point p
for (Point p : frame)
if (p != null)
p.setAngle(p0);
p0.angle = -1;
Collections.sort(frame); //sort by angle, ascending
hull.add(frame.get(0)); //push first two points on stack
hull.add(frame.get(1));
for (int i = 2; i < frame.size(); i++)
{
while (!frame.get(i).isLeft(hull.get(hull.size()-2), hull.get(hull.size()-1)))
hull.remove(hull.size()-1);
hull.add(frame.get(i));
}
}
static double dist(Point p, Point q)
{
double dx = p.x - q.x;
double dy = p.y - q.y;
return Math.hypot(dx, dy);
}
}
class Point implements Comparable<Point>
{
long x;
long y;
double angle;
double dist;
boolean dismissed = false;
public Point(int xx, int yy)
{
x = xx;
y = yy;
}
public void setAngle(Point p)
{
double dx = x - p.x;
double dy = y - p.y;
if (dy < 0)
throw new IllegalStateException();
else if ((dx == 0.0) && (dy == 0.0))
angle = 0;
else if (dx == 0.0)
angle = Math.PI / 2;
else if (dx < 0)
angle = Math.atan(Math.abs(dx) / dy) + Math.PI / 2;
else
angle = Math.atan(dy / dx);
//angle = angle / Math.PI * 180;
dist = Main.dist(this, p);
}
public int compareTo(Point p)
{
if (angle < p.angle)
return -1;
if (angle > p.angle)
return 1;
if (dist < p.dist)
return -1;
if (dist > p.dist)
return 1;
return 0;
}
public boolean isLeft(Point p0, Point p1)
{
return ((p1.x - p0.x) * (y - p0.y) - (x - p0.x) * (p1.y - p0.y)) >= 0;
}
}
class BufferedIntReader
{
byte[] buf = new byte[1024*32];
int pos = 0;
int len = 0;
public int nextInt()
{
int num = 0;
int chr;
boolean found = false;
boolean negative = false;
boolean stop = false;
while (!stop)
{
if (pos == len)
{
pos = 0;
try
{
len = System.in.read(buf);
} catch (java.io.IOException e)
{
throw new IllegalStateException(e); //wrap into runtime exception and throw
}
}
if (len == -1)
{
if (!found)
throw new IllegalStateException(new java.io.EOFException());
stop = true;
chr = ' ';
} else
{
chr = buf[pos];
pos++;
}
if ((chr >= '0') && (chr <= '9'))
{
num = num*10 + (chr - '0');
found = true;
} else if (chr == '-')
{
if (found)
{
// - after a number
// stop here, and push back - into the buffer, maybe sign of next number
stop = true;
pos--;
buf[pos] = '-';
} else
{
negative = true;
}
} else
{
if (found)
stop = true;
else
negative = false;
}
}
return (negative ? -num : num);
}
}