QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#267201 | #5106. Islands from the Sky | juampi | AC ✓ | 485ms | 82008kb | Java8 | 5.6kb | 2023-11-27 01:46:12 | 2023-11-27 01:46:12 |
Judging History
answer
// Arup Guha
// 11/16/2022
// Solution to 2021 WF Problem F: Islands from the Sky
import java.util.*;
public class F {
final public static double NOCOVER = 1000.0;
public static int nIslands;
public static int nFlights;
public static pt[][] islands;
public static lineseg[] flights;
public static double[][] angleCover;
public static void main(String[] args) {
Scanner stdin = new Scanner(System.in);
nIslands = stdin.nextInt();
islands = new pt[nIslands][];
nFlights = stdin.nextInt();
flights = new lineseg[nFlights];
// Read each island.
for (int i=0; i<nIslands; i++) {
int nPts = stdin.nextInt();
islands[i] = new pt[nPts];
// Read each pt.
for (int j=0; j<nPts; j++) {
long x = stdin.nextLong();
long y = stdin.nextLong();
islands[i][j] = new pt(x, y);
}
}
// Read in each flight.
for (int i=0; i<nFlights; i++) {
pt[] tmp = new pt[2];
for (int j=0; j<2; j++) {
double x = stdin.nextDouble();
double y = stdin.nextDouble();
double z = stdin.nextDouble();
tmp[j] = new pt(x, y, z);
}
flights[i] = new lineseg(tmp[0], tmp[1]);
}
// angleCover[i][j] will equal the angle at which flight i can completely
// survey island j. NOCOVER means it's impossible.
angleCover = new double[nFlights][nIslands];
for (int i=0; i<nFlights; i++) Arrays.fill(angleCover[i], NOCOVER);
ArrayList<Double> allAngles = new ArrayList<Double>();
// Fill this all in.
for (int i=0; i<nFlights; i++) {
for (int j=0; j<nIslands; j++) {
angleCover[i][j] = solve(i, j);
if (Math.abs(angleCover[i][j]-NOCOVER) > 1e-9)
allAngles.add(angleCover[i][j]);
}
}
// Get all possible answers and sort them.
int sz = allAngles.size();
Collections.sort(allAngles);
// In this case, it can't be done.
if (sz == 0 || !canDo(allAngles.get(sz-1)))
System.out.println("impossible");
// Binary search the answer.
else
System.out.println(binsearch(allAngles));
}
// Returns true iff angle works to cover all islands.
public static boolean canDo(double angle) {
// Try each islands.
for (int j=0; j<nIslands; j++) {
// See if at least one flight covers this island.
boolean covered = false;
for (int i=0; i<nFlights; i++) {
if (angleCover[i][j] < angle+1e-8) {
covered = true;
break;
}
}
// Oops, no one covered this island.
if (!covered) return false;
}
// Woo hoo, we covered the island.
return true;
}
// Binary searches which angle in angles is the smallest that works.
public static double binsearch(ArrayList<Double> angles) {
// Initial bounds.
int low = 0, high = angles.size()-1;
// Usual binary search.
while (low < high) {
// Go halfway.
int mid = (low+high)/2;
// Answer can't be bigger than mid.
if (canDo(angles.get(mid)))
high = mid;
// Answer must be greater than mid.
else
low = mid+1;
}
// Here is our answer!
return angles.get(low);
}
// Returns the minimum angle necessary for flight i to cover island j.
public static double solve(int i, int j) {
// Set up flight and island.
lineseg flight = flights[i];
pt[] island = islands[j];
pt perp = new pt(flights[i].d.y, -flights[i].d.x);
// Will update this.
double max = 0;
for (pt p: island) {
// Line from island point to line segment.
line mine = new line(p, perp);
// See if this line, perp to segment, hits the segment.
double[] info = mine.getD2D(flight);
double dist = info[0];
double beta = info[1];
// If you can't cover all the points, you can't cover the polygon.
if (dist < 0) return NOCOVER;
// How high up the plane is...
double myZ = flight.p.z + flight.d.z*beta;
double angle = Math.atan2(dist, myZ);
max = Math.max(angle, max);
}
// If we get here, this is what we want.
return Math.toDegrees(max);
}
}
class pt {
public double x;
public double y;
public double z;
public pt(double myx, double myy) {
x = myx;
y = myy;
z = 0;
}
public pt(double myx, double myy, double myz) {
x = myx;
y = myy;
z = myz;
}
public pt sub(pt other) {
return new pt(this.x-other.x, this.y-other.y, this.z-other.z);
}
public double mag2D() {
return Math.sqrt(x*x+y*y);
}
}
class lineseg {
public pt p;
public pt q;
public pt d;
public lineseg(pt start, pt end) {
p = start;
q = end;
d = q.sub(p);
}
}
class line {
public pt p;
public pt d;
public line(pt start, pt dir) {
p = start;
d = dir;
}
// Returns the perpendicular distance from this object to L. If the perpendicular
// doesn't hit L, then -1 is returned to indicate this.
public double[] getD2D(lineseg L) {
// p.x + lambda(d.x) = L.p.x + beta(L.d.x)
// p.y + lambda(d.y) = L.p.y + beta(L.d.y)
// lamb(d.x) - beta(L.d.x) = L.p.x-p.x
// lamb(d.y) - beta(L.d.y) = L.p.y-p.y
double det = -d.x*L.d.y + d.y*L.d.x;
// For me, these cases will never "count"
if (Math.abs(det) < 1e-9) return new double[]{-1,-1};
double betaNum = d.x*(L.p.y-p.y) - d.y*(L.p.x-p.x);
double beta = betaNum/det;
// There's an intersection, but not with the segment.
if (beta > 1+1e-9 || beta < -1e-9) return new double[]{-1,-1};
// Get lambda.
double lambNum = -(L.p.x-p.x)*L.d.y + (L.p.y-p.y)*L.d.x;
double lambda = lambNum/det;
// This is the distance to the line segment.
return new double[]{Math.abs(d.mag2D()*lambda), beta};
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 61ms
memory: 40664kb
input:
1 1 3 -5 0 5 0 0 5 -10 10 10 10 10 10
output:
45.0
result:
ok
Test #2:
score: 0
Accepted
time: 62ms
memory: 41936kb
input:
1 1 3 -5 0 5 0 0 5 -10 0 10 10 0 10
output:
26.56505117707799
result:
ok
Test #3:
score: 0
Accepted
time: 68ms
memory: 40804kb
input:
1 1 3 -5 0 5 0 0 5 0 10 10 10 0 10
output:
46.68614334171696
result:
ok
Test #4:
score: 0
Accepted
time: 71ms
memory: 40780kb
input:
1 1 3 -5 0 5 0 0 5 0 10 5 10 0 10
output:
59.4910411337972
result:
ok
Test #5:
score: 0
Accepted
time: 65ms
memory: 41432kb
input:
1 1 3 -5 0 5 0 0 5 0 10 20 -10 0 10
output:
31.219698447368387
result:
ok
Test #6:
score: 0
Accepted
time: 75ms
memory: 40980kb
input:
1 3 3 -5 0 5 0 0 5 -10 0 25 10 0 20 -5 10 10 10 -5 20 -4 1 100 5 10 100
output:
12.528807709151511
result:
ok
Test #7:
score: 0
Accepted
time: 65ms
memory: 39904kb
input:
1 2 4 0 0 20 0 20 40 0 40 -10 30 30 30 30 30 -10 10 30 30 10 30
output:
45.0
result:
ok
Test #8:
score: 0
Accepted
time: 70ms
memory: 40664kb
input:
1 4 4 0 0 20 0 20 40 0 40 -10 30 30 30 30 30 -10 20 30 30 20 30 -10 10 30 30 10 30 10 -10 30 10 50 30
output:
18.43494882292201
result:
ok
Test #9:
score: 0
Accepted
time: 69ms
memory: 39368kb
input:
1 2 4 0 0 40 0 40 40 0 40 10 10 10 20 20 20 30 10 10 10 30 20
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 63ms
memory: 39832kb
input:
1 3 4 0 0 20 0 20 40 0 40 -10 30 30 15 30 30 5 30 30 30 30 30 1 50 30 21 50 30
output:
impossible
result:
ok
Test #11:
score: 0
Accepted
time: 60ms
memory: 39972kb
input:
1 1 4 0 0 40 0 40 40 0 40 -100 -100 20 100 100 10
output:
63.66575215314687
result:
ok
Test #12:
score: 0
Accepted
time: 58ms
memory: 40060kb
input:
1 4 4 -10 -10 10 -10 10 10 -10 10 -100 0 10 100 0 10 0 100 10 0 -100 10 50 50 15 -50 -50 15 -50 50 15 50 -50 15
output:
43.31385665828304
result:
ok
Test #13:
score: 0
Accepted
time: 136ms
memory: 42720kb
input:
1 100 100 822286 0 856789 53904 986567 124632 629039 119995 732157 187986 691605 224716 728650 288493 591087 278144 801573 440668 425257 269876 614456 446428 424157 350893 645680 606334 406524 432904 545628 659551 359831 495265 367048 578376 251435 457360 319990 680014 336526 849968 214009 658652 23...
output:
53.790638431072466
result:
ok
Test #14:
score: 0
Accepted
time: 199ms
memory: 60040kb
input:
100 1 100 461002 481444 460618 481480 460584 481512 460833 481595 460670 481605 460545 481607 460942 481801 460526 481672 460912 481923 460765 481903 460505 481781 460430 481766 460589 481959 460593 482032 460477 481972 460440 481994 460510 482183 460285 481888 460387 482179 460246 481963 460303 482...
output:
impossible
result:
ok
Test #15:
score: 0
Accepted
time: 226ms
memory: 62416kb
input:
100 1 100 461002 481444 460618 481480 460584 481512 460833 481595 460670 481605 460545 481607 460942 481801 460526 481672 460912 481923 460765 481903 460505 481781 460430 481766 460589 481959 460593 482032 460477 481972 460440 481994 460510 482183 460285 481888 460387 482179 460246 481963 460303 482...
output:
33.69079560972086
result:
ok
Test #16:
score: 0
Accepted
time: 222ms
memory: 62160kb
input:
100 1 100 461002 481444 460618 481480 460584 481512 460833 481595 460670 481605 460545 481607 460942 481801 460526 481672 460912 481923 460765 481903 460505 481781 460430 481766 460589 481959 460593 482032 460477 481972 460440 481994 460510 482183 460285 481888 460387 482179 460246 481963 460303 482...
output:
66.40279664206592
result:
ok
Test #17:
score: 0
Accepted
time: 485ms
memory: 82008kb
input:
100 100 100 461002 481444 460618 481480 460584 481512 460833 481595 460670 481605 460545 481607 460942 481801 460526 481672 460912 481923 460765 481903 460505 481781 460430 481766 460589 481959 460593 482032 460477 481972 460440 481994 460510 482183 460285 481888 460387 482179 460246 481963 460303 4...
output:
4.1890016471314375
result:
ok
Test #18:
score: 0
Accepted
time: 266ms
memory: 67140kb
input:
100 11 100 461002 481444 460618 481480 460584 481512 460833 481595 460670 481605 460545 481607 460942 481801 460526 481672 460912 481923 460765 481903 460505 481781 460430 481766 460589 481959 460593 482032 460477 481972 460440 481994 460510 482183 460285 481888 460387 482179 460246 481963 460303 48...
output:
32.41192847717416
result:
ok
Test #19:
score: 0
Accepted
time: 420ms
memory: 81216kb
input:
100 90 100 461002 481444 460618 481480 460584 481512 460833 481595 460670 481605 460545 481607 460942 481801 460526 481672 460912 481923 460765 481903 460505 481781 460430 481766 460589 481959 460593 482032 460477 481972 460440 481994 460510 482183 460285 481888 460387 482179 460246 481963 460303 48...
output:
5.575448935978947
result:
ok
Extra Test:
score: 0
Extra Test Passed