挑战程序竞赛系列(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 条评论
登录 后参与评论

相关文章

来自专栏LeetCode

LeetCode 738. Monotone Increasing Digits

这是我开始选择的方法,非常直白,但是直白简单的方法往往不是最佳的解法,提交到LeetCode上,给我抛出一个超时,可见效率有多低。首先写一个函数,判断一个数是否...

1480
来自专栏赵俊的Java专栏

快乐数

2563
来自专栏用户2442861的专栏

JavaScript 正则表达式上——基本语法

JavaScript种正则表达式有两种定义方式,定义一个匹配类似 <%XXX%> 的字符串

701
来自专栏java初学

13.2 具体的集合

2789
来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4645
来自专栏小古哥的博客园

读书笔记-JavaScript面向对象编程(二)

第5章 原型 5.1 原型属性(所有函数拥有一个prototype属性,默认为空对象)   5.1.1 利用原型添加方法和属性 function Gadget(...

4468
来自专栏技术博客

C#基础知识系列十(集合)

  本节主要是来了解学习集合,以方便在程序编写时,什么地方该选用什么集合,让程序更健壮的运行起来。在学习了解集合之前,首先需要了解一些数据结构方面的知识。下面我...

1283
来自专栏cmazxiaoma的架构师之路

Java数据结构和算法(2)--《Java数据结构和算法》第二版 Robert lafore第二章【数组】编码作业

2123
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻OC对象的本质

4075
来自专栏Bingo的深度学习杂货店

Q503 Next Greater Element II

Given a circular array (the next element of the last element is the first elemen...

3346

扫码关注云+社区

领取腾讯云代金券