poj1066(叉乘的简单应用)
2024-08-25 00:30:55
做完了才发现,好像没有人和我的做法一样的,不过我怎么都觉得我的做法还是挺容易想的。
我的做法是:
把周围的方框按顺时针编号,然后对于每一条边,如果点出现在边的一侧,则把另一侧所有的点加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 ;
}
最新文章
- ASP.NET Aries 开源开发框架:开发指南(一)
- Python进程、线程
- linux C之access函数(转-追梦的小鸟)
- 转 Android中shape中的属性大全
- 上海洋码头(www.ymatou.com)急招技术人才(职位:互联网软件开发工程师,.NET网站架构师,Web前端开发工程师,高级测试工程师,产品经理)
- div+css(ul li)实现图片上文字下列表布局
- 有效解决js中添加border后动画bug问题
- Codeforces Round #208 (Div. 2) 358D Dima and Hares
- ROS理解roslaunch命令
- git - 简明指南(转)
- @InitBinde的作用
- 去掉matlab图片空白边缘
- 使用镜像仓库托管自己构建的Docker镜像
- hightcharts在移动端运用 FastClick后苹果上legend点击失效的解决办法
- 转每天一个linux命令(3):pwd命令
- CentOS / RHEL 7 : How to setup yum repository using locally mounted DVD
- 【做题】UOJ450 - 复读机——单位根反演
- 《WAP团队》作业四——基于原型的团队项目需求调研与分析
- yii2 Rbac实例 (做完以下这些 会有些小的报错,相信各位都能解决,大多数都是自己命名空间上的问题)。
- Github Issues
热门文章
- Swift入门(一)——基本的语法
- 什么是HotSpot VM &; 深入理解Java虚拟机 JVM
- Ubuntu16.04下安装googlechrome flash 插件和安装网易云音乐
- 面试题:如何在不使用临时变量temp的情况下交换两个整数的值?
- CentOS7关闭SELinux
- EffectiveJava(4)通过私有构造器强化不可实例化的能力
- 使用json-server搭建模拟api接口
- 倍福TwinCAT(贝福Beckhoff)基础教程2.1 TwinCAT常见类型简介
- Linux服务器大量向外发包问题排查
- 深入解析alloc/retain/release/dealloc实现