uva 1382 - Distant Galaxy

点击打开链接uva 1382

题意:给出平面上的n个点,找出一个矩形,使得边界上含有尽量多的点
思路:
1 很清楚,如果输入的n个点在同一行或者同一列的话那么ans = n。还有一种情况就是n个点的横坐标和纵坐标只有2种,那么这种情况ans = n。
2 对于这一题我们考虑的是枚举矩形的上下边界(纵坐标),然后利用其它的方法求左右边界,见下图


3 对于竖线i,我们用left[i]表示竖线左边位于上下边界的点数(不包括位于竖线i), on[i]表示竖线上位于上下边界之间的点数(和on2[i]的区别就是on[i]不统计位于上下边界的点数),这样给定左右边界i和j的话,矩形边界上的点数为left[j]+on2[j]+on[i]-left[i],当有边界j确定的时候,on[i]-left[i]要最大
4 那么我们枚举完上下边界后,我们利用O(n)的时间去求left[] , on[] , on2[],然后枚举有边界j,维护最大的on[i]-left[i]

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 110;
struct Node{
    int x;
    int y;
    bool operator<(const Node& s)const{
        return x < s.x;
    }
};
Node node[MAXN];
int n , numy[MAXN];

int solve(){
    sort(node , node+n);
    sort(numy , numy+n);
    int num = unique(numy , numy+n)-numy;
    if(num <= 2)//如果纵坐标最多只有2个那么ans = n
       return n;
    //枚举上下界
    int miny , maxy , ans;
    int left[MAXN] , on[MAXN] , on2[MAXN];
    ans = 0;
    for(int i = 0 ; i < num ; i++){
       for(int j = i+1 ; j < num ; j++){
           miny = numy[i];
           maxy = numy[j];
           //求left , on , on2数组;
           int k = -1;
           memset(left , 0 , sizeof(left));
           memset(on , 0 , sizeof(on));
           memset(on2 , 0 , sizeof(on2));
           for(int t = 0 ; t < n ; t++){
              if(!t || node[t].x != node[t-1].x){
                 k++;
                 left[k] = k == 0 ? 0 : left[k-1]+on2[k-1]-on[k-1];
              }
              if(node[t].y > miny && node[t].y < maxy)
                 on[k]++;
              if(node[t].y >= miny && node[t].y <= maxy)
                 on2[k]++;
           }
           if(k <= 1)//如果横坐标最多只有2个那么ans = n
              return n;
           int Max = 0;
           for(int t = 0 ; t <= k ; t++){
              ans = max(ans , left[t]+on2[t]+Max);
              Max = max(Max , on[t]-left[t]);
           }
       }
    }
    return ans;
}

int main(){
    int Case = 1;
    while(scanf("%d" , &n) && n){
         for(int i = 0 ; i < n ; i++){
            scanf("%d%d" , &node[i].x , &node[i].y);
            numy[i] = node[i].y;
         }
         printf("Case %d: %d\n" , Case++ , solve());
    }
    return 0;
}
时间: 2024-11-10 00:33:50

uva 1382 - Distant Galaxy的相关文章

Shanghai 2006 / UVa 1382 Distant Galaxy:枚举&amp;amp;扫描&amp;amp;动态维护

1382 - Distant Galaxy Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4128 You are observing a distant galaxy using a telescope above the Astronomy Tower

算法题:uva 1382

题目链接 1. 坐标值比较大,所以离散化坐标 2. 坐标的绝对值不超过10^9,说明可能有负数,所以把 全部坐标移动转换为正数(加上10^9) 3. mat[i][j] ,表示(0,0) (i, j)为对顶点矩形之 内包括边界上有多少个点. 4. 枚举矩形的上下界,然后选择左右边界. 对于确定的左边界left 和右边界right, 假设是下图的R3是left,  L3是right,那么数量为: L1 + L2 + L3 - (R1+R2) + R3. 为了要使得以L3为右边界的矩形上的点最多,那

Photoshop创建星战文字特效

  最终效果图 图00 1.设计文字背景 Step 1 创建950*550像素画布,将星空素材置入到背景图层上方,然后按画布大小调整尺寸. 图01 Step 2 双击星空图层,应用图层样式中的颜色叠加,设置混合模式为正片叠底,颜色为#a6a6a6. 图02 Step 3 这样会让星空背景稍微变暗一点.在图层面板,点击添加纯色调整图层. 图03 Step 4 选用颜色#fced82,设置调整图层混合模式为正片叠底,不透明度为25%. 图04 2.创建文字 Step 1 下载教程提供的SF Dist

Photoshop制作非常大气的金色星战标题立体字

效果字制作分为三个部分:背景.字体效果.装饰.背景使用了一张与主题相关的星空素材,微调了颜色:字体部分用了多个图层,每一层用不同的样式增加描边.浮雕.纹理等:最后加上一些星光装饰即可. 最终效果 1.创建950*550像素画布,将星空素材置入到背景图层上方,然后按画布大小调整尺寸. 2.双击星空图层,应用图层样式中的颜色叠加,设置混合模式为正片叠底,颜色为#a6a6a6. 3.这样会让星空背景稍微变暗一点.在图层面板,点击添加纯色调整图层. 4.选用颜色#fced82,设置调整图层混合模式为正片

Photoshop制作大气的金色星战标题立体字

  效果字制作分为三个部分:背景.字体效果.装饰.背景使用了一张与主题相关的星空素材,微调了颜色;字体部分用了多个图层,每一层用不同的样式增加描边.浮雕.纹理等;最后加上一些星光装饰即可. 最终效果 1.创建950*550像素画布,将星空素材置入到背景图层上方,然后按画布大小调整尺寸. 2.双击星空图层,应用图层样式中的颜色叠加,设置混合模式为正片叠底,颜色为#a6a6a6. 3.这样会让星空背景稍微变暗一点.在图层面板,点击添加纯色调整图层. 4.选用颜色#fced82,设置调整图层混合模式为

Photoshop设计金色星球大战金属文字效果制作教程

给各位Photoshop软件的使用者们来详细的分享一下设计金色星球大战金属文字效果的制作教程. 教程分享: 1.设计文字背景 Step 1 创建950*550像素画布,将星空素材置入到背景图层上方,然后按画布大小调整尺寸.   图01 Step 2 双击星空图层,应用图层样式中的颜色叠加,设置混合模式为正片叠底,颜色为#a6a6a6.   图02 Step 3 这样会让星空背景稍微变暗一点.在图层面板,点击添加纯色调整图层.   图03 Step 4 选用颜色#fced82,设置调整图层混合模式

UVA 10085:The most distant state

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=110&page=show_problem&problem=1026 类型: 隐式图搜索 原题: The 8-puzzle is a square tray in which eight square tiles are placed. The remaining ninth square is uncove

uva 10085 - The most distant state bfs+map

10085 - The most distant state    类似8数码的一道题,只是求变化次数最多的一种,也就是队列最后一层    用的bfs+map,map保存方向和这个节点的权值,懒得搞hash函数,就用map顺便当做hash用了    用字符串s存状态,s[9]表示0的位置    最后的方向dfs输出.    这题WA了一次,输出忘加case了--   /* author:jxy lang:C/C++ university:China,Xidian University **If

uva 10085 10085 - The most distant state

点击打开链接 题目意思: 八数码问题的变形,给定一个初始状态要求找到该状态很够到达的最远的状态,输出这个最远状态和路径.(特判,答案不唯一) 解题思路:  做过八数码的同学肯定觉得这一题很水吧,确实是的,要求我么找到最远的,我么知道广搜是只要有一个节点能够扩展就会继续往下扩展,那么当广搜不能在扩展的时候就是到最远的状态(不理解的可以自己画画图想想),其它就是八数码的一些注意问题了,见我博客就有详解. 代码: #include <algorithm> #include <iostream&