幾何核心判斷

點在線上

向量叉積為 0：(B - A) × (P - A) == 0。代碼中用斜率比較並處理垂直線（分母為 0）特殊情況。

點在線左側（順時針視角）

對有向邊 A→B，點 P 在左側 ⇔ 叉積 (B - A) × (P - A) > 0。代碼通過比較 P.x 與線上同 y 座標處的 x 實現（避免浮點誤差用 float 斜率）。

Java 完整實現

Point.java

package com.justinsoft.polygon.model;

public class Point implements Comparable {
    private final int x, y;
    private final int dist2; // 距離原點平方

    public Point(int x, int y) {
        this.x = x; this.y = y;
        this.dist2 = x * x + y * y;
    }
    public int getX() { return x; }
    public int getY() { return y; }
    public int getDist2() { return dist2; }

    @Override public int compareTo(Point o) { return Integer.compare(dist2, o.dist2); }
    @Override public String toString() { return "Point[x=" + x + ",y=" + y + "]"; }
}

Line.java（有向邊）

package com.justinsoft.polygon.model;

public class Line {
    private final Point start, end;
    private final float slope; // 斜率，垂直線標記為 0 並另行處理

    public Line(Point s, Point e) {
        this.start = s; this.end = e;
        this.slope = calcSlope(s, e);
    }
    private static float calcSlope(Point a, Point b) {
        int dx = b.getX() - a.getX();
        int dy = b.getY() - a.getY();
        return dx == 0 ? 0 : (float) dy / dx;
    }

    // 點是否在線上
    public boolean contains(Point p) {
        float k = calcSlope(p, start);
        if (k == 0) { // 垂直線或水平線特判
            int dx = p.getX() - start.getX();
            return dx == 0 ? p.getX() == end.getX() : p.getY() == end.getY();
        }
        return k == slope;
    }

    // 點是否在線左側（順時針多邊形內部在右側）
    public boolean hasLeftPoint(Point p) {
        if (slope == 0) { // 垂直線
            return end.getX() == start.getX() ? p.getX() < start.getX() : p.getY() < start.getY();
        }
        // 線上對應 p.y 的 x 座標
        float xOnLine = (p.getY() - start.getY()) / slope + start.getX();
        return p.getX() < xOnLine;
    }
    public Point getStart() { return start; }
    public Point getEnd() { return end; }
    public float getSlope() { return slope; }
}

PolygonSort.java（主算法）

package com.justinsoft.polygon;

import com.justinsoft.polygon.model.*;
import java.util.*;

public class PolygonSort {
    private static final String ERR = "ERROR";
    private static final String SEP = ",";

    public static String findConvexPolygon(String input) {
        try {
            List pts = parse(input);
            if (hasCollinear(pts)) return ERR;

            Point p0 = Collections.min(pts); // 最近原點
            pts.remove(p0);
            Point p1 = pts.remove(0); // 任取一點

            List chain = new ArrayList<>();
            chain.add(new Line(p0, p1));

            for (Point p : pts) insertPoint(chain, p);

            // 閉合
            chain.add(new Line(chain.get(chain.size()-1).getEnd(), p0));

            if (!isConvex(chain)) return ERR;
            return format(chain);
        } catch (Exception e) { return ERR; }
    }

    private static List parse(String s) {
        String[] a = s.split(SEP);
        if (a.length % 2 != 0 || a.length < 6) throw new IllegalArgumentException();
        List res = new ArrayList<>();
        for (int i = 0; i < a.length; i += 2)
            res.add(new Point(Integer.parseInt(a[i]), Integer.parseInt(a[i+1])));
        return res;
    }

    private static boolean hasCollinear(List pts) {
        List tmp = new ArrayList<>(pts);
        for (int i = 0; i < tmp.size(); ++i) {
            Point a = tmp.get(i);
            for (int j = i+1; j < tmp.size(); ++j) {
                Line L = new Line(a, tmp.get(j));
                for (int k = j+1; k < tmp.size(); ++k)
                    if (L.contains(tmp.get(k))) return true;
            }
        }
        return false;
    }

    private static void insertPoint(List chain, Point p) {
        for (int i = 0; i < chain.size(); ++i) {
            Line L = chain.get(i);
            if (L.hasLeftPoint(p)) {
                chain.remove(i);
                chain.add(i, new Line(p, L.getEnd()));
                chain.add(i, new Line(L.getStart(), p));
                return;
            }
        }
        // 全在右側 -> 接尾部
        chain.add(new Line(chain.get(chain.size()-1).getEnd(), p));
    }

    private static boolean isConvex(List chain) {
        List all = new ArrayList<>();
        for (Line L : chain) all.add(L.getStart());

        for (int i = 0; i < chain.size(); ++i) {
            Line L = chain.get(i);
            boolean hasLeft = false, hasRight = false;
            for (Point p : all) {
                if (p == L.getStart() || p == L.getEnd()) continue;
                if (L.hasLeftPoint(p)) hasLeft = true;
                else hasRight = true;
                if (hasLeft && hasRight) return false; // 凹
            }
        }
        return true;
    }

    private static String format(List chain) {
        StringBuilder sb = new StringBuilder();
        for (Line L : chain) {
            sb.append(L.getStart().getX()).append(SEP)
              .append(L.getStart().getY()).append(SEP);
        }
        if (sb.length() > 0) sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }
}

單元測試

package com.justinsoft.polygon;

import org.junit.Test;
import static org.junit.Assert.*;

public class PolygonSortTest {
    @Test public void test1() { assertEquals("ERROR", PolygonSort.findConvexPolygon("1,2,3")); }
    @Test public void test2() { assertEquals("0,0,0,1,1,1", PolygonSort.findConvexPolygon("0,0,1,1,0,1")); }
    @Test public void test3() { assertEquals("0,0,0,1,1,1,1,0", PolygonSort.findConvexPolygon("0,0,1,1,0,1,1,0")); }
    @Test public void test4() { assertEquals("ERROR", PolygonSort.findConvexPolygon("0,0,1,1,0,3,3,0")); }
}

複雜度與避坑指南

• 時間複雜度：O(n^2)（共線檢測 + 增量插入 + 凸性驗證），n 為點數，滿足題目規模。
• 整數座標用 int，斜率用 float，注意垂直線（dx=0）單獨處理避免除零。
• 共線判斷需覆蓋所有三元組，O(n^3) 但點數較小可接受；大規模可用凸包算法預處理。
• 增量插入法構建的邊鏈天然保持順時針序，起始點固定為最近原點點，滿足輸出要求。