package lujing;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class WangfanpathJisuan {
    
    /**
     * 坐标点类，使用记录处理提高精度控制
     */
    private static class Point {
        final double x;
        final double y;
        final int originalIndex; // 记录原始位置，便于调试
        
        Point(double x, double y, int index) {
            this.x = x;
            this.y = y;
            this.originalIndex = index;
        }
        
        Point(double x, double y) {
            this(x, y, -1);
        }
        
        double distanceTo(Point other) {
            if (other == null) return Double.MAX_VALUE;
            double dx = this.x - other.x;
            double dy = this.y - other.y;
            return Math.sqrt(dx * dx + dy * dy);
        }
        
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Point point = (Point) obj;
            // 使用1e-6的精度判断相等，比直接比较double更稳定
            return Math.abs(point.x - x) < 1e-6 && Math.abs(point.y - y) < 1e-6;
        }
        
        @Override
        public int hashCode() {
            // 使用固定精度进行哈希计算，确保精度范围内相等的点有相同哈希值
            long xBits = Double.doubleToLongBits(Math.round(x * 1e6) / 1e6);
            long yBits = Double.doubleToLongBits(Math.round(y * 1e6) / 1e6);
            return (int)(xBits ^ (xBits >>> 32) ^ yBits ^ (yBits >>> 32));
        }
        
        @Override
        public String toString() {
            return String.format("%.3f,%.3f", x, y);
        }
        
        public String toString(int precision) {
            return String.format("%." + precision + "f,%." + precision + "f", x, y);
        }
    }
    
    /**
     * 线段类，用于计算点到线段的距离
     */
    private static class LineSegment {
        final Point start;
        final Point end;
        final double length;
        
        LineSegment(Point start, Point end) {
            this.start = start;
            this.end = end;
            this.length = start.distanceTo(end);
        }
        
        /**
         * 计算点到线段的垂直距离
         */
        double perpendicularDistance(Point point) {
            if (length == 0) {
                return point.distanceTo(start);
            }
            
            // 使用向量方法计算投影距离
            double x1 = start.x, y1 = start.y;
            double x2 = end.x, y2 = end.y;
            double x0 = point.x, y0 = point.y;
            
            // 计算点到直线距离公式
            double numerator = Math.abs((y2 - y1) * x0 - (x2 - x1) * y0 + x2 * y1 - y2 * x1);
            double denominator = Math.sqrt((y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1));
            
            return numerator / denominator;
        }
        
        /**
         * 判断点是否在线段的边界框内（用于判断是否在线段上）
         */
        boolean isPointInBoundingBox(Point point) {
            double minX = Math.min(start.x, end.x);
            double maxX = Math.max(start.x, end.x);
            double minY = Math.min(start.y, end.y);
            double maxY = Math.max(start.y, end.y);
            
            return point.x >= minX && point.x <= maxX && 
                   point.y >= minY && point.y <= maxY;
        }
    }
    
    /**
     * 优化配置类
     */
    public static class OptimizationConfig {
        private double distanceTolerance = 0.1;       // 距离容差（米）
        private double angleTolerance = 1.0;          // 角度容差（度）
        private int outputPrecision = 3;              // 输出精度（小数位数）
        private boolean keepEndpoints = true;         // 是否保留端点
        private boolean useFastSimplify = false;      // 是否使用快速简化算法
        
        public OptimizationConfig() {}
        
        public OptimizationConfig setDistanceTolerance(double tolerance) {
            this.distanceTolerance = Math.max(0.01, tolerance); // 最小0.01米
            return this;
        }
        
        public OptimizationConfig setAngleTolerance(double degrees) {
            this.angleTolerance = Math.max(0.1, Math.min(degrees, 45)); // 限制在0.1-45度
            return this;
        }
        
        public OptimizationConfig setOutputPrecision(int precision) {
            this.outputPrecision = Math.max(0, Math.min(precision, 8)); // 限制在0-8位
            return this;
        }
        
        public OptimizationConfig setKeepEndpoints(boolean keep) {
            this.keepEndpoints = keep;
            return this;
        }
        
        public OptimizationConfig setUseFastSimplify(boolean useFast) {
            this.useFastSimplify = useFast;
            return this;
        }
    }
    
    private OptimizationConfig config;
    
    public WangfanpathJisuan() {
        this.config = new OptimizationConfig();
    }
    
    public WangfanpathJisuan(OptimizationConfig config) {
        this.config = config;
    }
    
    /**
     * 主优化方法
     */
    public String optimizePath(String pathStr) {
        return optimizePath(pathStr, this.config);
    }
    
    /**
     * 带配置的优化方法
     */
    public String optimizePath(String pathStr, OptimizationConfig config) {
        if (pathStr == null || pathStr.trim().isEmpty()) {
            return "";
        }
        
        List<Point> points = parsePoints(pathStr);
        if (points.size() <= 2) {
            return pointsToString(points, config.outputPrecision);
        }
        
        // 执行优化流水线
        List<Point> result = optimizationPipeline(points, config);
        
        return pointsToString(result, config.outputPrecision);
    }
    
    /**
     * 优化流水线：按顺序执行多个优化步骤
     */
    private List<Point> optimizationPipeline(List<Point> points, OptimizationConfig config) {
        List<Point> result = new ArrayList<>(points);
        
        // 步骤1: 去除连续重复点
        result = removeConsecutiveDuplicates(result);
        
        // 步骤2: 根据配置选择简化算法
        if (config.useFastSimplify) {
            result = fastSimplify(result, config.distanceTolerance, config.angleTolerance);
        } else {
            result = douglasPeuckerSimplify(result, config.distanceTolerance);
        }
        
        // 步骤3: 确保端点（可选）
        if (config.keepEndpoints && result.size() > 1) {
            ensureEndpoints(points, result);
        }
        
        return result;
    }
    
    /**
     * 解析坐标点，带位置索引
     */
    private List<Point> parsePoints(String pathStr) {
        List<Point> points = new ArrayList<>();
        String[] pointStrs = pathStr.split(";");
        
        for (int i = 0; i < pointStrs.length; i++) {
            String pointStr = pointStrs[i].trim();
            if (pointStr.isEmpty()) continue;
            
            String[] xy = pointStr.split(",");
            if (xy.length != 2) continue;
            
            try {
                double x = Double.parseDouble(xy[0].trim());
                double y = Double.parseDouble(xy[1].trim());
                points.add(new Point(x, y, i));
            } catch (NumberFormatException e) {
                // 跳过格式错误的点，记录日志（实际使用时可添加日志）
                continue;
            }
        }
        
        return points;
    }
    
    /**
     * 去除连续重复点（优化版）
     */
    private List<Point> removeConsecutiveDuplicates(List<Point> points) {
        if (points.size() <= 1) {
            return new ArrayList<>(points);
        }
        
        List<Point> result = new ArrayList<>(points.size());
        result.add(points.get(0));
        
        for (int i = 1; i < points.size(); i++) {
            Point current = points.get(i);
            Point last = result.get(result.size() - 1);
            
            // 使用距离判断是否重复，考虑浮点精度
            if (current.distanceTo(last) > config.distanceTolerance * 0.1) {
                result.add(current);
            }
            // 如果距离很小但实际是不同的点（浮点误差），仍保留
            else if (!current.equals(last)) {
                result.add(current);
            }
        }
        
        return result;
    }
    
    /**
     * 快速简化算法（结合距离和角度判断）
     */
    private List<Point> fastSimplify(List<Point> points, double distanceTolerance, double angleToleranceDeg) {
        if (points.size() < 3) {
            return new ArrayList<>(points);
        }
        
        List<Point> result = new ArrayList<>();
        result.add(points.get(0));
        
        int i = 1;
        while (i < points.size() - 1) {
            Point prev = result.get(result.size() - 1);
            Point current = points.get(i);
            Point next = points.get(i + 1);
            
            // 检查距离条件
            double distToPrev = current.distanceTo(prev);
            double distToNext = current.distanceTo(next);
            
            // 检查角度条件（将角度容差转换为弧度）
            double angleToleranceRad = Math.toRadians(angleToleranceDeg);
            double angle = calculateAngle(prev, current, next);
            
            // 如果点距离前一点或后一点很近，或者三点形成的角度接近180度（共线），则剔除当前点
            if (distToPrev < distanceTolerance || 
                distToNext < distanceTolerance ||
                Math.abs(Math.PI - angle) < angleToleranceRad) {
                i++; // 跳过当前点
            } else {
                result.add(current);
                i++;
            }
        }
        
        // 添加最后一个点
        if (points.size() > 1) {
            result.add(points.get(points.size() - 1));
        }
        
        return result;
    }
    
    /**
     * 计算三点形成的角度（以中间点为顶点）
     */
    private double calculateAngle(Point a, Point b, Point c) {
        double baX = a.x - b.x;
        double baY = a.y - b.y;
        double bcX = c.x - b.x;
        double bcY = c.y - b.y;
        
        double dotProduct = baX * bcX + baY * bcY;
        double magnitudeBA = Math.sqrt(baX * baX + baY * baY);
        double magnitudeBC = Math.sqrt(bcX * bcX + bcY * bcY);
        
        if (magnitudeBA == 0 || magnitudeBC == 0) {
            return 0;
        }
        
        double cosAngle = dotProduct / (magnitudeBA * magnitudeBC);
        // 处理浮点误差
        cosAngle = Math.max(-1.0, Math.min(1.0, cosAngle));
        
        return Math.acos(cosAngle);
    }
    
    /**
     * 道格拉斯-普克算法（迭代实现，避免递归栈溢出）
     */
    private List<Point> douglasPeuckerSimplify(List<Point> points, double epsilon) {
        if (points.size() <= 2) {
            return new ArrayList<>(points);
        }
        
        // 使用位标记数组，比递归更节省内存
        boolean[] keep = new boolean[points.size()];
        keep[0] = keep[points.size() - 1] = true;
        
        // 使用栈来模拟递归
        LinkedList<int[]> stack = new LinkedList<>();
        stack.push(new int[]{0, points.size() - 1});
        
        while (!stack.isEmpty()) {
            int[] range = stack.pop();
            int start = range[0];
            int end = range[1];
            
            if (end - start < 2) {
                continue;
            }
            
            double maxDistance = 0;
            int maxIndex = start;
            
            Point startPoint = points.get(start);
            Point endPoint = points.get(end);
            LineSegment segment = new LineSegment(startPoint, endPoint);
            
            // 寻找离线段最远的点
            for (int i = start + 1; i < end; i++) {
                double distance = segment.perpendicularDistance(points.get(i));
                if (distance > maxDistance) {
                    maxDistance = distance;
                    maxIndex = i;
                }
            }
            
            // 如果最远点距离大于容差，则处理两侧
            if (maxDistance > epsilon) {
                keep[maxIndex] = true;
                if (maxIndex - start > 1) {
                    stack.push(new int[]{start, maxIndex});
                }
                if (end - maxIndex > 1) {
                    stack.push(new int[]{maxIndex, end});
                }
            }
        }
        
        // 收集保留的点
        List<Point> result = new ArrayList<>();
        for (int i = 0; i < points.size(); i++) {
            if (keep[i]) {
                result.add(points.get(i));
            }
        }
        
        return result;
    }
    
    /**
     * 确保端点被保留
     */
    private void ensureEndpoints(List<Point> original, List<Point> simplified) {
        if (original.isEmpty() || simplified.isEmpty()) return;
        
        Point firstOriginal = original.get(0);
        Point lastOriginal = original.get(original.size() - 1);
        
        // 检查首点
        if (!simplified.get(0).equals(firstOriginal)) {
            simplified.add(0, firstOriginal);
        }
        
        // 检查尾点
        Point lastSimplified = simplified.get(simplified.size() - 1);
        if (!lastSimplified.equals(lastOriginal)) {
            simplified.add(lastOriginal);
        }
    }
    
    /**
     * 将点列表转换为字符串
     */
    private String pointsToString(List<Point> points, int precision) {
        if (points.isEmpty()) {
            return "";
        }
        
        return points.stream()
            .map(p -> p.toString(precision))
            .collect(Collectors.joining(";"));
    }
    
    /**
     * 批处理优化方法
     */
    public List<String> optimizePaths(List<String> pathStrings, OptimizationConfig config) {
        return pathStrings.stream()
            .map(path -> optimizePath(path, config))
            .collect(Collectors.toList());
    }
    
    /**
     * 性能统计信息
     */
    public static class OptimizationStats {
        public final int originalPoints;
        public final int optimizedPoints;
        public final double reductionPercentage;
        public final long processingTimeMs;
        
        public OptimizationStats(int original, int optimized, long timeMs) {
            this.originalPoints = original;
            this.optimizedPoints = optimized;
            this.reductionPercentage = original > 0 ? 
                (1.0 - (double)optimized / original) * 100 : 0;
            this.processingTimeMs = timeMs;
        }
        
        @Override
        public String toString() {
            return String.format("优化统计: %d -> %d 点 (减少 %.1f%%)，耗时 %dms",
                originalPoints, optimizedPoints, reductionPercentage, processingTimeMs);
        }
    }
    
    /**
     * 带统计信息的优化方法
     */
    public OptimizationResult optimizePathWithStats(String pathStr, OptimizationConfig config) {
        long startTime = System.currentTimeMillis();
        
        if (pathStr == null || pathStr.trim().isEmpty()) {
            return new OptimizationResult("", new OptimizationStats(0, 0, 0));
        }
        
        List<Point> originalPoints = parsePoints(pathStr);
        String optimizedPath = optimizePath(pathStr, config);
        List<Point> optimizedPoints = parsePoints(optimizedPath);
        
        long endTime = System.currentTimeMillis();
        
        OptimizationStats stats = new OptimizationStats(
            originalPoints.size(), 
            optimizedPoints.size(), 
            endTime - startTime
        );
        
        return new OptimizationResult(optimizedPath, stats);
    }
    
    /**
     * 优化结果封装类
     */
    public static class OptimizationResult {
        public final String optimizedPath;
        public final OptimizationStats stats;
        
        public OptimizationResult(String path, OptimizationStats stats) {
            this.optimizedPath = path;
            this.stats = stats;
        }
    }
    
   
    
    /**
     * 生成测试路径
     */
    private static String generateTestPath(int pointCount) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < pointCount; i++) {
            sb.append(i).append(",").append(i % 10);
            if (i < pointCount - 1) {
                sb.append(";");
            }
        }
        return sb.toString();
    }
    
    /**
     * 性能测试
     */
    private static void testPerformance(WangfanpathJisuan calculator, int iterations) {
        String testPath = generateTestPath(1000);
        
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < iterations; i++) {
            calculator.optimizePath(testPath);
        }
        long endTime = System.currentTimeMillis();
        
        System.out.printf("处理 %d 次，每次1000点，总耗时: %dms，平均每次: %.2fms\n",
            iterations, endTime - startTime, 
            (double)(endTime - startTime) / iterations);
    }
}