250227 Oil

Jongleee·2025년 2월 27일
0

TIL

목록 보기
822/863
static class Point implements Comparable<Point> {
	long x, y;
	int value;

	Point(long x, long y, int value) {
		this.x = x;
		this.y = y;
		this.value = value;
	}

	@Override
	public int compareTo(Point other) {
		long ccw = (x - origin.x) * (other.y - origin.y) - (y - origin.y) * (other.x - origin.x);
		return ccw < 0 ? -1 : value(other, ccw);
	}

	private int value(Point other, long ccw) {
		return ccw > 0 ? 1 : Integer.compare(other.value, value);
	}
}

private static Point origin;

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(br.readLine());
	Point[] points = new Point[2 * n];

	for (int i = 0; i < n; i++) {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x0 = Integer.parseInt(st.nextToken());
		int x1 = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		points[i] = new Point(Math.min(x0, x1), y, Math.abs(x0 - x1));
		points[i + n] = new Point(Math.max(x0, x1), y, -Math.abs(x0 - x1));
	}

	System.out.println(findMaxValue(n, points));
}

private static int findMaxValue(int n, Point[] points) {
	int maxResult = 0;

	for (int i = 0; i < n; i++) {
		origin = points[i];
		List<Point> sortedPoints = new ArrayList<>();

		for (int j = 0; j < 2 * n; j++) {
			if (origin.y < points[j].y) {
				sortedPoints.add(points[j]);
			} else if (origin.y > points[j].y) {
				sortedPoints.add(new Point(
						2 * origin.x - points[j].x,
						2 * origin.y - points[j].y,
						-points[j].value));
			}
		}

		Collections.sort(sortedPoints);
		maxResult = Math.max(maxResult, getMaxAccumulatedValue(sortedPoints, origin.value));
	}

	return maxResult;
}

private static int getMaxAccumulatedValue(List<Point> sortedPoints, int startValue) {
	int maxAccumulated = startValue;
	int currentSum = startValue;

	for (Point p : sortedPoints) {
		currentSum += p.value;
		maxAccumulated = Math.max(maxAccumulated, currentSum);
	}

	return maxAccumulated;
}

출처:https://www.acmicpc.net/problem/12771

0개의 댓글

관련 채용 정보