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

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

传送门:POJ 1981: Circle and Points

题意:

平面上有N个点,给定半径为1的圆,最多能在圆内点的个数。

这种题目很大特色在于,如果枚举圆的圆心,那么在偌大的空间中,有无数个圆,显然是不现实的。所以得考虑极限情况,也就是找出一种特殊的状态,更新它们的集合,能够获得答案。

此题的极限情况为:当两个点在一个圆上时,最大值一定在于这种情况。因此,我们可以枚举两个点构成的圆,并且计算该圆内有多少个点,更新最大值即可。

证明: 假设存在一个圆,圆内包含了最大个数的点,稍微移动圆的圆心不会发生任何变化,直到移动至出现两个点在圆上时,最大值依旧没有发生变化,但一旦再移动时,最大个数将减小。所以最大值一定存在于某两个点i和j构成的圆,且i和j在圆上or圆内。

参考至: http://www.hankcs.com/program/algorithm/poj-1981-circle-and-points.html

所以我们只需要计算出两个点构成的极角,当然都得以i为坐标原点。

  • atan2的角度为j和i的纵坐标与横坐标之比,取反tan。
  • acos的角度为d/2,图中很清楚了。
  • 所以两个极限角即为atan2 - acos和atan2 + acos。

最后,对极角排个序,遇到起始点加1,遇到终点减1,不断更新重叠区域个数的最大值即可。

代码如下:

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.StringTokenizer;

public class Main{

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

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

    static final int MAX_N = 302;

    class P {
        double x;
        double y;
        P(double x, double y){
            this.x = x;
            this.y = y;
        }
    }

    class PolarAngle implements Comparable<PolarAngle>{

        double  angle;
        boolean flag;
        PolarAngle(double angle, boolean flag){
            this.angle = angle;
            this.flag  = flag;
        }
        @Override
        public int compareTo(PolarAngle that) {
            return Double.compare(this.angle, that.angle);
        }
    }

    P[] points = new P[MAX_N];
    PolarAngle[] pa = new PolarAngle[2 * MAX_N];

    int N;
    int ans;

    double dist(P a, P b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    void solve() {
        ans = 1;
        for (int i = 0; i < N; ++i) {
            int m = 0;
            for (int j = 0; j < N; ++j) {
                double d = 0;
                if (i != j && (d = dist(points[i], points[j])) <= 2.0) {
                    double theta = Math.acos(d / 2);
                    double phi   = Math.atan2(points[j].y - points[i].y, points[j].x - points[i].x);
                    pa[m++] = new PolarAngle(phi - theta, true);  // start
                    pa[m++] = new PolarAngle(phi + theta, false); // end;
                }
            }

            Arrays.sort(pa, 0, m);

            int sum = 1;
            for (int j = 0; j < m; ++j) {
                if (pa[j].flag) {
                    sum ++;
                }
                else {
                    sum --;
                }
                ans = Math.max(ans, sum);
            }
        }
    }

    void read() {
        while (true) {
            N = ni();
            if (N == 0) break;
            for (int i = 0; i < N; ++i) {
                points[i] = new P(nd(), nd());
            }
            ans = 0;
            solve();
            out.println(ans);
        }
    }

    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 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

厚土Go学习笔记 | 28. go语言没有类 却可以在结构体或任意类型定义方法

在go语言中没有类。可是,是有方法的。 给结构体定义方法,在对应的 func 和方法名之间,加上方法的接收者就可以了。 比如,我们定义了一个结构体 type V...

3728
来自专栏数据结构与算法

P1774 最接近神的人_NOI导刊2010提高(02)

题目描述 破解了符文之语,小FF开启了通往地下的道路。当他走到最底层时,发现正前方有一扇巨石门,门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“...

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

最大子数组差

题目链接: 45. 最大子数组差 给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。 返回这个最...

3404
来自专栏用户画像

计算两个经纬度的距离

702
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

662
来自专栏机器学习入门

POJ 刷题系列:2965. The Pilots Brothers' refrigerator

POJ 刷题系列:2965. The Pilots Brothers’ refrigerator 传送门:POJ 2965. The Pilots Brothe...

1816
来自专栏小樱的经验随笔

Codeforces 791B Bear and Friendship Condition(DFS,有向图)

B. Bear and Friendship Condition time limit per test:1 second memory limit per t...

3379
来自专栏专知

Numpy教程第2部分 - 数据分析的重要功能

【导读】Numpy是python数据分析和科学计算的核心软件包。 上次介绍了numpy的一些基础操作。例如如何创建一个array,如何提取array元素,重塑(...

3919
来自专栏余林丰

1.比较排序之冒泡排序

  冒泡排序可以说是在排序算法中最为入门级别的算法之一了。因为其简单易于理解,常在课堂中作为排序的入门算法。   冒泡排序见名生意,其排序过程如同水里的泡一般由...

1716
来自专栏猿人谷

C++ STL算法系列5---equal() , mismatch()

equal和mismatch算法的功能是比较容器中的两个区间内的元素。这两个算法各有3个参数first1,last1和first2.如果对 于区间[first1...

2148

扫码关注云+社区