做完了才发现,好像没有人和我的做法一样的,不过我怎么都觉得我的做法还是挺容易想的。

我的做法是:

把周围的方框按顺时针编号,然后对于每一条边,如果点出现在边的一侧,则把另一侧所有的点加1,这样最后统计最小值+1即可。

离散化一下 O(n)

//
// main.cpp
// poj1066
//
// Created by 陈加寿 on 15/12/30.
// Copyright (c) 2015年 chenhuan001. All rights reserved.
// #include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std; struct line
{
int x1,y1;
int x2,y2;
}g[]; int save[]; int chg(int x,int y)
{
if( y== ) return x;
if( x== ) return +-y;
if( y== ) return + -x;
return +y;
} int main(int argc, const char * argv[]) {
int n;
while( scanf("%d",&n)!=EOF )
{
for(int i=;i<n;i++)
{
scanf("%d%d%d%d",&g[i].x1,&g[i].y1,&g[i].x2,&g[i].y2);
g[i].x1 *= ;
g[i].y1 *= ;
g[i].x2 *= ;
g[i].y2 *= ;
}
double x,y;
scanf("%lf%lf",&x,&y);
x*=;
y*=;
memset(save,,sizeof(save));
//以防万一,还是坐标乘2先
int num=;
for(int i=;i<n;i++)
{
if( chg( g[i].x1,g[i].y1 ) > chg(g[i].x2,g[i].y2) )
{
swap(g[i].x1,g[i].x2);
swap(g[i].y1,g[i].y2);
} int b,d;
b= chg( g[i].x1,g[i].y1 );
d= chg( g[i].x2,g[i].y2 ); double p1x,p1y,p2x,p2y;
p1x = g[i].x1-x;
p1y = g[i].y1-y;
p2x = g[i].x2-x;
p2y = g[i].y2-y; if( p1x*p2y - p1y*p2x > )
{
num++;
for(int j=b+;j<=d-;j++) save[j]--;
}
else
{
for(int j=b;j<=d;j++) save[j]++;
}
}
int mi=;
for(int i=;i<;i++) mi = min(mi ,save[i] );
printf("Number of doors = %d\n",mi+num+);
}
return ;
}

最新文章

  1. ASP.NET Aries 开源开发框架:开发指南(一)
  2. Python进程、线程
  3. linux C之access函数(转-追梦的小鸟)
  4. 转 Android中shape中的属性大全
  5. 上海洋码头(www.ymatou.com)急招技术人才(职位:互联网软件开发工程师,.NET网站架构师,Web前端开发工程师,高级测试工程师,产品经理)
  6. div+css(ul li)实现图片上文字下列表布局
  7. 有效解决js中添加border后动画bug问题
  8. Codeforces Round #208 (Div. 2) 358D Dima and Hares
  9. ROS理解roslaunch命令
  10. git - 简明指南(转)
  11. @InitBinde的作用
  12. 去掉matlab图片空白边缘
  13. 使用镜像仓库托管自己构建的Docker镜像
  14. hightcharts在移动端运用 FastClick后苹果上legend点击失效的解决办法
  15. 转每天一个linux命令(3):pwd命令
  16. CentOS / RHEL 7 : How to setup yum repository using locally mounted DVD
  17. 【做题】UOJ450 - 复读机——单位根反演
  18. 《WAP团队》作业四——基于原型的团队项目需求调研与分析
  19. yii2 Rbac实例 (做完以下这些 会有些小的报错,相信各位都能解决,大多数都是自己命名空间上的问题)。
  20. Github Issues

热门文章

  1. Swift入门(一)——基本的语法
  2. 什么是HotSpot VM &amp; 深入理解Java虚拟机 JVM
  3. Ubuntu16.04下安装googlechrome flash 插件和安装网易云音乐
  4. 面试题:如何在不使用临时变量temp的情况下交换两个整数的值?
  5. CentOS7关闭SELinux
  6. EffectiveJava(4)通过私有构造器强化不可实例化的能力
  7. 使用json-server搭建模拟api接口
  8. 倍福TwinCAT(贝福Beckhoff)基础教程2.1 TwinCAT常见类型简介
  9. Linux服务器大量向外发包问题排查
  10. 深入解析alloc/retain/release/dealloc实现