文档章节

8_21_2013_Problem D: BUREK_纯模拟

電泡泡
 電泡泡
发布于 2013/08/21 19:50
字数 564
阅读 31
收藏 0

Problem D: BUREK

Time Limit: 1 Sec   Memory Limit: 32 MB
Submit: 22   Solved: 14
[ Submit][ Status][ Web Board]

Description

Baker  Crumble  has  just  baked N triangular  burek
2
 pastries.  Each  pastry  can  be  represented  in  the 
Cartesian coordinate system as a triangle with vertices in integer coordinate points. 
The baker's mischievous son Joey has just taken a large knife and started to cut the pastries. Each cut 
that Joey makes corresponds to a horizontal (y = c) or vertical (x = c) line in the coordinate  system. 
Help the baker assess the damage caused by Joey's pastry cutting. Your task is to determine, for each 
Joey's cut, how many pastries are affected (such that both the left and right parts of the cut pastry have 
areas greater than zero).

Input

The first line of input contains the positive integer N (2 ≤ N ≤ 100 000), the number of burek pastries. 
Each of the following N lines contains six nonnegative integers smaller than 10
6
. These numbers are, in 
order, the coordinates (x1, y1), (x2, y2), (x3, y3) of the three pastry-triangle vertices. The three vertices will 
not all be on the same line. The pastries can touch as well as overlap. 
The following line contains the positive integer M (2 ≤ M ≤ 100 000), the number of cuts. 
Each of the following M lines contains a single cut line equation: “x = c” or “y = c” (note the spaces 
around the equals sign), where c is a nonnegative integer smaller than 10
6
.

Output

For each cut, output a line containing the required number of cut pastries.

Sample Input

3 1 0 0 2 2 2 1 3 3 5 4 0 5 4 4 5 4 4 4 x = 4 x = 1 y = 3 y = 1 4 2 7 6 0 0 5 7 1 7 10 11 11 5 10 2 9 6 8 1 9 10 10 4 1 4 y = 6 x = 2 x = 4 x = 9

Sample Output

0 1 1 2 3 2 3 2

HINT

In test data worth at least 40 points, M ≤ 300. 

In  test  data  worth an additional 40 points, the  vertex  coordinates  of  all  triangles  will  be  smaller  than 

1000.

#include <iostream>
using namespace std;

struct point{
	int x, y;
};
struct tri{
	point p[4]; 
}t[100010];

int compare(int k, char line, int num){
	int dis[5];
	if(line=='x'){
		for(int i=1; i<=3; i++){
			dis[i]=t[k].p[i].x-num;
		}
		if( dis[1]>=0&&dis[2]>=0&&dis[3]>=0 ||
		    dis[1]<=0&&dis[2]<=0&&dis[3]<=0
		  )
		  {
			return 0;
		  }
	}
	else{
		for(int i=1; i<=3; i++){
			dis[i]=t[k].p[i].y-num;
		}
		if( dis[1]>=0&&dis[2]>=0&&dis[3]>=0 ||
		    dis[1]<=0&&dis[2]<=0&&dis[3]<=0
		  )
			return 0;
		
	}
	return 1;
}
 
int 
main()
{
	int n, m, num, sum, ans;
	char line, s[10];
	char ch;
	while(cin>>n){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=3; j++){
				cin>>t[i].p[j].x>>t[i].p[j].y;
			}
		}
		cin>>m;
		for(int i=1; i<=m; i++){
			ans=0;
			cin>>line>>ch>>num;
			//cout<<line<<ch<<num<<endl;
			for(int i=1; i<=n; i++){
				sum=compare(i, line, num);
				//cout<<sum;
				ans+=sum;
			}
			//cout<<"**";
			cout<<ans<<endl;
		}
	}
	return 0;
}


© 著作权归作者所有

共有 人打赏支持
電泡泡
粉丝 23
博文 183
码字总数 69717
作品 0
衡阳
私信 提问
有什么工具能获取到全盘文件名还有文件的根路径?

看标题 这是我在网上找的一款名为FileList命令行工具,XP系统下用的,能显示文件名,大小,修改时间,访问时间,创建时间,所有者,路径。但是有乱码,就不能导入PostgreSQL数据库了。大家集...

fumingfu
2013/03/12
329
6
hi 林峰~~在线急等求解,万分感谢!!!

@Kener-林峰 你好,想跟你请教个问题: 我阅读了API发现在echart上中对横坐标为日期的情况都是穷举 如: xAxis : [ { type : 'category', boundaryGap : true, axisTick: {onGap:false}, sp...

jessya
2014/05/08
179
1
数据库启动之NOMOUNT

1.启动数据库:STARTUP命令后,执行顺序如下 首先使用服务器上的SPFILESID文件启动实例,如未找到,使用服务器上默认的SPFILE启动实例;如未找到默认SPFILE,使用INITSID文件启动实例,如仍未...

长平狐
2013/09/17
276
0
AppleScript 判断按键事件的脚本文章收集

AppleScript support for SplitPanes 来自:http://code.google.com/p/iterm2/issues/detail?id=559 Reported by samantha...@gmail.com , Jan 29, 2011 Hi, I would like to be able to sc......

FreeBlues
2013/12/17
0
0
用Nodejs连接MySQL

从零开始nodejs系列文章, 将介绍如何利Javascript做为服务端脚本,通过Nodejs框架web开发。Nodejs框架是基于V8的引擎,是目前速度最快的 Javascript引擎。chrome浏览器就基于V8,同时打开2...

WolfX
2016/02/28
43
0

没有更多内容

加载失败,请刷新页面

加载更多

filebeat multiline配置(转)

使用filebeat5.0.1版本,用filebeat作为日志收集工具时: java日志格式需要多行匹配,在filebeat配置文件中添加: ### Multiline options # Mutiline can be used for log messages spanning...

xiaomin0322
26分钟前
1
0
ConstraintLayout的基本使用

<?xml version="1.0" encoding="utf-8"?><android.support.constraint.ConstraintLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="ht......

SuShine
29分钟前
1
0
ActiveMQ多个消费者消费不均匀问题

如果客户端处理很慢的话,Broker会在之前发送消息的反馈之前,继续发送新的消息到客户端。如果客户端依旧很慢的话,没有得到确认反馈的消息会持续增长。在这种情况下,Broker有可能会停止发送...

编程SHA
31分钟前
1
0
【机器学习PAI实战】—— 玩转人工智能之综述

模型训练与在线预测服务、推荐算法四部曲、机器学习PAI实战、更多精彩,尽在开发者分会场 【机器学习PAI实战】—— 玩转人工智能之商品价格预测 【机器学习PAI实战】—— 玩转人工智能之你最...

阿里云云栖社区
34分钟前
1
0
根据国务院2019年劳动节假期安排五一放假四天 免费节假日api第一时间调整

根据国务院发布http://www.gov.cn/zhengce/content/2019-03/22/content_5375877.htm 以下为原文 国务院办公厅关于调整 2019年劳动节假期安排的通知 国办发明电〔2019〕3号 各省、自治区、直辖...

xiaogg
39分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部