作者RockLee (Now of all times)
看板Prob_Solve
標題[問題] Google Code Jam 2008, EMEA Semifinal-A
時間Sun Apr 1 16:20:49 2012
題目敘述網址:
http://code.google.com/codejam/contest/32010/dashboard
看了當初參賽者上傳的 code 還是不懂 ~><~
有高手可以開示一下 dgozman 的算法的意思嗎?
或是這題您會怎麼解? <_.._>
[dgozman's code in Java, 原始版]
http://www.go-hero.net/jam/08/name/dgozman
EMEA Onsite -> Scaled Triangle -> large
[dgozman's code in Java, 簡化版, 刪除不必要的 permutation]
import java.io.*;
import java.util.*;
public class TaskA
{
public static void main(String[] args) throws IOException {new
TaskA().run();}
BufferedReader br;
PrintWriter pw;
private void run() throws IOException
{
br = new BufferedReader(new FileReader("a.in"));
pw = new PrintWriter("a.out");
int tests = Integer.parseInt(br.readLine().trim());
for (int test = 1; test <= tests; test++)
{
pw.print("Case #" + test + ": ");
runtest();
}
br.close();
pw.close();
}
private void runtest() throws IOException
{
long[] x1 = new long[3];
long[] y1 = new long[3];
long[] x2 = new long[3];
long[] y2 = new long[3];
StringTokenizer st = new StringTokenizer(br.readLine());
x1[0] = Long.parseLong(st.nextToken());
y1[0] = Long.parseLong(st.nextToken());
x1[1] = Long.parseLong(st.nextToken());
y1[1] = Long.parseLong(st.nextToken());
x1[2] = Long.parseLong(st.nextToken());
y1[2] = Long.parseLong(st.nextToken());
st = new StringTokenizer(br.readLine());
x2[0] = Long.parseLong(st.nextToken());
y2[0] = Long.parseLong(st.nextToken());
x2[1] = Long.parseLong(st.nextToken());
y2[1] = Long.parseLong(st.nextToken());
x2[2] = Long.parseLong(st.nextToken());
y2[2] = Long.parseLong(st.nextToken());
long xn = x1[0];
long yn = y1[0];
long axn = x1[1] - x1[0];
long ayn = y1[1] - y1[0];
long bxn = x1[2] - x1[0];
long byn = y1[2] - y1[0];
long xm = x2[0];
long ym = y2[0];
long axm = x2[1] - x2[0];
long aym = y2[1] - y2[0];
long bxm = x2[2] - x2[0];
long bym = y2[2] - y2[0];
long a = axn - axm;
long b = bxn - bxm;
long c = xm - xn;
long d = ayn - aym;
long e = byn - bym;
long f = ym - yn;
double p = 0.0;
double q = 0.0;
if (a * e != b * d)
{
p = (1.0 * c * e - b * f) / (1.0 * a * e - b * d);
q = (1.0 * a * f - c * d) / (1.0 * a * e - b * d);
}
pw.printf("%.6f %.6f\n", xn + p * axn + q * bxn, yn + p * ayn + q * byn);
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.30.95