TopBoy

武汉赛区解题报告 by ACRush

http://www.acrush.cn/index.php?title=%E6%AD%A6%E6%B1%89%E7%8E%B0%E5%9C%BA%E8%B5%9B%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A_by_ACRush

我找的一些简单题，基本上不用考虑什么算法，适合ACM入门的朋友，或者想练习编程的朋友

题目由易到难排序

POJ 1000 基本运算
POJ 1004 循环运算
POJ 2027 比较判断
POJ 2350 Above Average 求平均值，输出大于平均值的比例
POJ 2301 Beat the Spread 给出两个数的和与差，求这两个数
POJ 1552 Doubles  输入判断和循环
POJ 2105 IP Address 字符串处理，进制转换
POJ 3650 The Seven Percent Solution 简单的字符串处理
POJ 1005 I Think I Need a Houseboat 圆面积公式
POJ 1046 Color Me Less 循环，枚举
POJ 1028 Web Navigation 栈的简单应用
（更新中。。。）

http://acm.pku.edu.cn/JudgeOnline/problem?id=2318

题意：
     有一矩形，N条直线(直线不相交)把矩形分成N+1个区间，然后给定M个点，求矩形每个区间内有多少个点，如下图

算法：
     简单题，只要对每个点求出所在的区间然后计数，求区间时使用二分找到这个点右边或者左边的第一条直线即可，复杂度M*logN

代码：

#include<iostream>

using namespace std;

 

#define MAX 5005

int n, m;

double x1, y1, x2, y2;

double u[MAX], l[MAX];

double k[MAX];    // 斜率

double h;

int count[MAX];

 

void bsearch(double x, double y)

{

      int ma = n, mi = 0, mid;

      double rx;

      double ydis = y – y1;

      while(ma > mi)

      {

            mid = (ma+mi)>>1;

            rx = k[mid] * ydis + u[mid];

            if(rx<x)mi = mid+1;

            else if(rx>x)ma = mid;

      }

      count[ma]++;

}

int main()

{

      int i;

      double x, y;

      while(scanf(“%d”,&n)==1 && n)

      {

            memset(count, 0, sizeof(count));

            scanf(“%d %lf %lf %lf %lf”,&m,&x1,&y1,&x2,&y2);

            h = y2 – y1;

            for(i=0;i<n;++i)

            {

                  scanf(“%lf%lf”,&u[i], &l[i]);

                  k[i] = (l[i]-u[i])/h;

            }

            u[n] = x2; l[n] = x2; k[n] = 0;

            for(i=0;i<m;++i)

            {

                  scanf(“%lf%lf”,&x,&y);

                  bsearch(x, y);

            }

            for(i=0;i<=n;++i)

                  printf(“%d: %d\n”,i,count[i]);

            printf(“\n”);

      }

      return 0;

}