import java.util.ArrayList;
import java.util.List;

class Point {
    double latitude; // Enlem
    double longitude; // Boylam
    long timestamp;

    public Point(double latitude, double longitude, long timestamp) {
        this.latitude = latitude;
        this.longitude = longitude;
        this.timestamp = timestamp;
    }
}

public class DouglasPeuckerWithTimeAndLocation {
    public static List<Point> simplify(List<Point> points, double tolerance, long minTimeInterval) {
        if (points == null || points.size() < 3)
            return points;

        int firstIndex = 0;
        int lastIndex = points.size() - 1;
        List<Integer> indexesToKeep = new ArrayList<>();
        simplifyRecursive(points, firstIndex, lastIndex, tolerance, minTimeInterval, indexesToKeep);

        List<Point> simplifiedPoints = new ArrayList<>();
        for (int index : indexesToKeep) {
            simplifiedPoints.add(points.get(index));
        }
        return simplifiedPoints;
    }

    private static void simplifyRecursive(List<Point> points, int firstIndex, int lastIndex,
                                          double tolerance, long minTimeInterval, List<Integer> indexesToKeep) {
        double maxDistance = 0;
        int indexFarthest = 0;

        Point startPoint = points.get(firstIndex);
        Point endPoint = points.get(lastIndex);

        for (int i = firstIndex + 1; i < lastIndex; i++) {
            double distance = findPerpendicularDistance(points.get(i), startPoint, endPoint);
            if (distance > maxDistance) {
                maxDistance = distance;
                indexFarthest = i;
            }
        }

        if (maxDistance > tolerance) {
            indexesToKeep.add(indexFarthest);
            simplifyRecursive(points, firstIndex, indexFarthest, tolerance, minTimeInterval, indexesToKeep);
            simplifyRecursive(points, indexFarthest, lastIndex, tolerance, minTimeInterval, indexesToKeep);
        } else {
            if (endPoint.timestamp - startPoint.timestamp >= minTimeInterval) {
                indexesToKeep.add(lastIndex);
            }
        }
    }

    private static double findPerpendicularDistance(Point point, Point startPoint, Point endPoint) {
        double numerator = Math.abs((endPoint.longitude - startPoint.longitude) * point.latitude - (endPoint.latitude - startPoint.latitude) * point.longitude + endPoint.latitude * startPoint.longitude - endPoint.longitude * startPoint.latitude);
        double denominator = Math.sqrt(Math.pow(endPoint.longitude - startPoint.longitude, 2) + Math.pow(endPoint.latitude - startPoint.latitude, 2));
        return numerator / denominator;
    }

    public static void main(String[] args) {
        List<Point> points = new ArrayList<>();
        // Örnek noktalar ekleyin
        points.add(new Point(40.7128, -74.0060, System.currentTimeMillis())); // New York
        points.add(new Point(34.0522, -118.2437, System.currentTimeMillis() + 300000)); // Los Angeles (5 dakika sonra)
        points.add(new Point(51.5074, -0.1278, System.currentTimeMillis() + 600000)); // Londra (10 dakika sonra)
        points.add(new Point(35.6895, 139.6917, System.currentTimeMillis() + 1200000)); // Tokyo (20 dakika sonra)
        // ... diğer noktaları ekle

        // Douglas-Peucker sadeleştirme
        List<Point> simplifiedPoints = simplify(points, 0.1, 300000); // Tolerans ve minimum zaman aralığını belirleyin

        // Sadeleştirilmiş noktaları yazdırın
        for (Point point : simplifiedPoints) {
            System.out.println("(" + point.latitude + ", " + point.longitude + ") - " + point.timestamp);
        }
    }
}