1.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest
* Problem: 11122 - Tri Tri
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2063
*
*
* Method : Interpolation
* Status : Accepted
* Runtime: 0.184
*
* @author Evgeni Pavlidis
* @version 1.0, 09/11/2010
*/
import java.io.*;
import java.util.*;
class Point
{
double x,y;
Point(double x,double y)
{ this.x = x; this.y = y; }
public String toString()
{ return String.format("(%.2f,%.2f)", x, y); }
Point add(double dx, double dy)
{
x += dx;
y += dy;
return this;
}
}
class Triangle
{
static final double e = 1e-10;
Point[] p = new Point[3];
Triangle(Point a,Point b, Point c)
{ p[0] = a; p[1] = b; p[2] = c; }
boolean containsPoint(Point a)
{
for(int i = 0; i < 3; i++)
if(direction(p[i], p[(i+1)%3], p[(i+2)%3]) != direction(p[i],p[(i+1)%3],a))
return false;
return true;
}
boolean collidesWith(Triangle o)
{
// check mid point
Point g = new Point((o.p[0].x + o.p[1].x + o.p[2].x)/3 , (o.p[0].y + o.p[1].y + o.p[2].y)/3 );
if(containsPoint(g))
return true;
int s = 1000;
for(int i = 0; i < 3; i++)
{
Point point = new Point(o.p[i].x, o.p[i].y);
double dx = (o.p[(i+1)%3].x - o.p[i].x) / s;
double dy = (o.p[(i+1)%3].y - o.p[i].y) / s;
for(int j = 1; j < s; j++)
if(containsPoint(point.add(dx,dy)))
return true;
}
return false;
}
static long direction(Point m, Point a, Point b)
{
double result = (a.x - m.x)*(b.y - m.y) - (b.x - m.x)*(a.y - m.y);
if(result < -e)
return -1;
if(result > e)
return 1;
return 0;
}
}
class Main
{
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int nextInt() throws IOException
{
st.nextToken();
return (int) st.nval;
}
public static void main(String...args) throws IOException
{
int testCases = nextInt();
Triangle t1,t2;
for(int tc = 1; tc <= testCases; tc++)
{
t1 = new Triangle(new Point(nextInt(), nextInt()),
new Point(nextInt(), nextInt()),
new Point(nextInt(), nextInt()) );
t2 = new Triangle(new Point(nextInt(), nextInt()),
new Point(nextInt(), nextInt()),
new Point(nextInt(), nextInt()) );
System.out.printf("pair %d: %s\n", tc, ( (t1.collidesWith(t2) || t2.collidesWith(t1))? "yes": "no" ) );
}
}
}
2.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 11122 TriTri
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2063
*
* @author Anton Pavlushko, IBB7B,
* @version 1.0, 02/11/2010
*
* Status : Accepted
* Runtime: 0.116
*/
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String current_line, empty = "";
int number, border, i, j, length, number_local;
int primes [];
Iterator iter;
int znak,count,count_already,multiply;
StringTokenizer input_string;
boolean status, at_least_one;
double try_it, base_log;
String tri_1[], tri_2[], reply;
int a[],b[],c[],d[],e[],f[],ab[],bc[],ca[],line_count,d_count,e_count,f_count;
try {
current_line=in.readLine();
input_string = new StringTokenizer(current_line);
count=Integer.parseInt(input_string.nextToken());
tri_1 = new String[count+1];
tri_2 = new String[count+1];
a = new int[2];
b = new int[2];
c = new int[2];
d = new int[2];
e = new int[2];
f = new int[2];
ab = new int[3];
bc = new int[3];
ca = new int[3];
for(i=0;i<count;i++) {
in.readLine();
tri_1[i]=in.readLine();
tri_2[i]=in.readLine();
}
for(i=0;i<count;i++) {
reply="yes";
input_string = new StringTokenizer(tri_1[i]);
a[0]= Integer.parseInt(input_string.nextToken());
a[1]= Integer.parseInt(input_string.nextToken());
b[0]= Integer.parseInt(input_string.nextToken());
b[1]= Integer.parseInt(input_string.nextToken());
c[0]= Integer.parseInt(input_string.nextToken());
c[1]= Integer.parseInt(input_string.nextToken());
input_string = new StringTokenizer(tri_2[i]);
d[0]= Integer.parseInt(input_string.nextToken());
d[1]= Integer.parseInt(input_string.nextToken());
e[0]= Integer.parseInt(input_string.nextToken());
e[1]= Integer.parseInt(input_string.nextToken());
f[0]= Integer.parseInt(input_string.nextToken());
f[1]= Integer.parseInt(input_string.nextToken());
ab[0]=a[1]-b[1];
ab[1]=b[0]-a[0];
ab[2]=a[0]*b[1]-a[1]*b[0];
bc[0]=b[1]-c[1];
bc[1]=c[0]-b[0];
bc[2]=b[0]*c[1]-b[1]*c[0];
ca[0]=c[1]-a[1];
ca[1]=a[0]-c[0];
ca[2]=c[0]*a[1]-c[1]*a[0];
if (reply=="yes") {//AB
line_count=ab[0]*c[0]+ab[1]*c[1]+ab[2];
d_count=ab[0]*d[0]+ab[1]*d[1]+ab[2];
e_count=ab[0]*e[0]+ab[1]*e[1]+ab[2];
f_count=ab[0]*f[0]+ab[1]*f[1]+ab[2];
if ((line_count>0 && d_count<=0 && e_count<=0 && f_count<=0) ||
(line_count<0 && d_count>=0 && e_count>=0 && f_count>=0)) reply="no";
}
if (reply=="yes") {//BC
line_count=bc[0]*a[0]+bc[1]*a[1]+bc[2];
d_count=bc[0]*d[0]+bc[1]*d[1]+bc[2];
e_count=bc[0]*e[0]+bc[1]*e[1]+bc[2];
f_count=bc[0]*f[0]+bc[1]*f[1]+bc[2];
if ((line_count>0 && d_count<=0 && e_count<=0 && f_count<=0) ||
(line_count<0 && d_count>=0 && e_count>=0 && f_count>=0)) reply="no";
}
if (reply=="yes") {//CA
line_count=ca[0]*b[0]+ca[1]*b[1]+ca[2];
d_count=ca[0]*d[0]+ca[1]*d[1]+ca[2];
e_count=ca[0]*e[0]+ca[1]*e[1]+ca[2];
f_count=ca[0]*f[0]+ca[1]*f[1]+ca[2];
if ((line_count>0 && d_count<=0 && e_count<=0 && f_count<=0) ||
(line_count<0 && d_count>=0 && e_count>=0 && f_count>=0)) reply="no";
}
System.out.println("pair "+(i+1)+": "+reply);
}
} // end try
catch (IOException ee) {
System.err.println("Error: " + ee);
}
}
}