挑战程序竞赛系列(89):3.6平面扫描(3)

挑战程序竞赛系列(89):3.6平面扫描(3)

传送门:POJ 3292: Rectilinear polygon

题意参考hankcs: http://www.hankcs.com/program/algorithm/poj-3293-rectilinear-polygon.html

题意:

直角多边形:给定N个点,问是否能组成直角多边形(每个顶点都与另外两个顶点构成直角,每条边都平行于坐标轴),并求出周长?

思路参考: http://www.cnblogs.com/ZefengYao/p/7470984.html

平面扫描,按照x轴扫描可以获得所有竖边的长度和,按y轴的同理,先讨论x轴的情况,将点按照x坐标大小排序后,同一列上的点按照y坐标从小到大排序,之后再观察多边形每一列的特性,可以发现每一列上点必定偶数个,相邻两个配对可以成为一条边,若出现奇数条边,肯定是构不成多边形的。按y轴扫描也是相同做法。其次还要判断是否有横竖边相交的情况以及是否有洞(图是否连通)即可。

讲的很清楚了,此题的trick在于如何实现水平线与垂直线的相交判断,记录哪些信息可以检测出相交问题呢?

首先按照x轴扫描,不会出现相交的线,所以只需要把每条线段信息记录在一种数据结构即可,方便y轴扫描时判断相交。显然,给定一条水平线的横坐标的两端,我们只需要比较该区间内是否有垂直线与之相交,采用TreeSet维护x轴垂直线的有序,接着只要在扫描y轴时,知道两个端点,就可以拿到该区间内的垂直线逐个判断即可。

代码如下:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main{

    String INPUT = "./data/judge/201709/P3293.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    static final int MAX_N = 100000 + 16;

    class Point {
        int x;
        int y;
        Point[] nxt;
        int tot;

        Point(int x, int y){
            this.x = x;
            this.y = y;
            this.tot = 0;
            this.nxt = new Point[2];
        }

        void add(Point a) {
            nxt[tot++] = a;
        }

        @Override
        public boolean equals(Object obj) {
            Point p = (Point) obj;
            return p.x == x && p.y == y;
        }

        @Override
        public String toString() {
            return "(" + x + " " + y + ")";
        }
    }

    class Line implements Comparable<Line>{
        int x;
        int y0;
        int y1;

        Point[] ps;

        Line (int x, int y0, int y1){
            this.x = x;
            this.y0 = y0;
            this.y1 = y1;
            ps = new Point[2];
        }

        int distance() {
            int dx = ps[0].x - ps[1].x;
            int dy = ps[0].y - ps[1].y;
            return Math.abs(dx) + Math.abs(dy);
        }

        @Override
        public int compareTo(Line o) {
            return this.x - o.x;
        }

        @Override
        public boolean equals(Object obj) {
            Line o = (Line) obj;
            return o.x == x && o.y0 == y0 && o.y1 == y1;
        }

        @Override
        public String toString() {
            return ps[0].toString() + "->" + ps[1].toString();
        }
    }

    int N;
    Point[] ps;

    boolean intersect(Point a, Point b, Point c, Point d) {  // 左 a 右 b 下 c 上 d
        return a.x < c.x && b.x > c.x && c.y < a.y && d.y > a.y;
    }

    long solve() {

        TreeSet<Line> lines = new TreeSet<Line>();
        long ans = 0;

        Arrays.sort(ps, 0, N, new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                return o1.x != o2.x ? o1.x - o2.x : o1.y - o2.y;
            }
        });

        for (int i = 0; i < N; ++i) {  // 按x轴方向扫描

            int j = i;
            while (j < N && ps[j].x == ps[i].x) ++j;
            if (((j - i) & 1) != 0) return -1;
            else {
                for (int k = i; k < j; k += 2) {
                    ps[k].add(ps[k + 1]);
                    ps[k + 1].add(ps[k]);
                    Line line = new Line(ps[k].x, ps[k].y, ps[k + 1].y);
                    line.ps[0] = ps[k];
                    line.ps[1] = ps[k + 1];
                    ans += line.distance();
                    lines.add(line);
                }
            }
            i = j - 1;
        }

        Arrays.sort(ps, 0, N, new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                return o1.y != o2.y ? o1.y - o2.y : o1.x - o2.x;
            }
        });

        for (int i = 0; i < N; ++i) { //按y轴方向扫描
            int j = i;
            while (j < N && ps[j].y == ps[i].y) ++j;
            if (((j - i) & 1) != 0) return -1;
            else {
                for (int k = i; k < j; k +=2) {
                    ps[k].add(ps[k + 1]);
                    ps[k + 1].add(ps[k]);

                    Line l1 = new Line(ps[k].x, 0, 0);
                    Line l2 = new Line(ps[k + 1].x, 0, 0);
                    l1.ps[0] = ps[k];
                    l1.ps[1] = ps[k + 1];

                    for (Line line : lines.subSet(l1, l2)) {
                        if (intersect(l1.ps[0], l1.ps[1], line.ps[0], line.ps[1])) return -1;
                    }
                    ans += l1.distance();
                }
            }
            i = j - 1;
        }

        Point crt = ps[0];
        Point pre = null;
        int cnt = 0;
        do {
            cnt ++;
            Point tmp = crt;
            if (pre == crt.nxt[0]) {
                crt = crt.nxt[1];
            }
            else{
                crt = crt.nxt[0];
            }
            pre = tmp;
        }
        while (!crt.equals(ps[0]));
        return cnt == N ? ans : -1;
    }

    void read() {
        int T = ni();
        while (T --> 0) {
            N = ni();
            ps= new Point[N];

            for (int i = 0; i < N; ++i) {
                int x = ni();
                int y = ni();
                ps[i] = new Point(x, y);
            }

            out.println(solve());
        }
    }

    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        read();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏冷冷

SpringMVC 之 ModelAndView和ModelAttribute的使用

ModelAndView解释 : This class merely holds both to make it possible for a controll...

1815
来自专栏Python小屋

Python使用AES算法进行加解密

本文要点在于Python扩展库pycrypto实现了大量密码学算法,可以拿来直接使用。 import string import random from Cry...

2636
来自专栏Hongten

java开发_MD5_加密算法

732
来自专栏机器学习入门

挑战程序竞赛系列(88):3.6平面扫描(2)

挑战程序竞赛系列(88):3.6平面扫描(2) 传送门:POJ 3168: Barn Expansion 题意: 求不重叠的矩形个数。 当然,题意是说求能够被...

1755
来自专栏机器学习入门

挑战程序竞赛系列(87):3.6平面扫描(1)

挑战程序竞赛系列(87):3.6平面扫描(1) 传送门:POJ 2932: Coneology 题意: 平面上有N个两两没有公共点的圆,i号圆的圆心在(xi,...

1928
来自专栏一个会写诗的程序员的博客

从爬取的文章 HTML 中提取出中文关键字

https://github.com/KotlinSpringBoot/saber

726
来自专栏机器学习入门

挑战程序竞赛系列(72):4.7高度数组(2)

挑战程序竞赛系列(72):4.7高度数组(2) 传送门:POJ 3415: Common Substrings 题意: 公共子串:统计A和B长度不小于K的公共...

17710
来自专栏xingoo, 一个梦想做发明家的程序员

Dijkstra

迪杰斯特拉算法是典型的求解最短路径的方法。 优点,时间复杂度为O(n2),主要思想就是遍历邻居,找到路径最短的邻居,添加到路径信息里面。再更新这个添加点,是否能...

1757
来自专栏码匠的流水账

聊聊resilience4j的CircuitBreakerStateMachine

本文主要研究一下resilience4j的CircuitBreakerStateMachine

462
来自专栏机器学习入门

挑战程序竞赛系列(85):3.6极限情况(2)

挑战程序竞赛系列(85):3.6极限情况(2) 传送门:POJ 1418: Viva Confetti 题意: 礼花:Confetti 是一些大小不一的彩色圆...

1845

扫码关注云+社区