| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 51408 | spencercompton | Bulldozer (JOI17_bulldozer) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class bulldozer {
public static class Pair implements Comparable<Pair>{
public double loc;
public long val;
public Pair(double a, long b){
loc = a;
val = b;
}
public int compareTo(Pair o) {
return Double.compare(loc, o.loc);
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long ans = 0L;
long[] x = new long[n];
long[] y = new long[n];
long[] v = new long[n];
for(int i = 0; i<n; i++) {
x[i] = in.nextLong();
y[i] = in.nextLong();
v[i] = in.nextLong();
}
for(int i = 0; i<n; i++) {
ans = Math.max(ans, v[i]);
for(int j = i+1; j<n; j++) {
ArrayList<Pair> li = new ArrayList<Pair>();
for(int k = 0; k<n; k++) {
long cross = (y[k]-y[j])*(x[j]-x[i]) - (y[j]-y[i])*(x[k]-x[j]);
double dist = Line2D.ptLineDist(x[i], y[i], x[j], y[j], x[k], y[k]);
if(cross<=0) {
li.add(new Pair(dist,v[k]));
}
else {
li.add(new Pair(-dist,v[k]));
}
}
Collections.sort(li);
int f = -1;
int s = -1;
for(int k = 0; k<n; k++) {
if(Math.abs(li.get(k).loc)<1e-7) {
if(f==-1) {
f = k;
}
s = k;
}
}
if(f==-1) {
int[] ar = new int[1];
System.out.println("WHHAT " + ar[5]);
}
long bestPre = 0L;
long curPre = 0L;
for(int k = f-1; k>=0; k--) {
curPre += li.get(k).val;
bestPre = Math.max(bestPre, curPre);
}
long bestPost = 0L;
long curPost = 0L;
for(int k = s+1; k<n; k++) {
curPost += li.get(k).val;
bestPost = Math.max(bestPost, curPost);
}
ans = Math.max(v[i]+v[j]+bestPre+bestPost, ans);
}
}
System.out.println(ans);
}
}