分类目录归档:计算几何

CodeforcesRound#367 Div.2

A. Beru-taxi

Vasiliy lives at point (a, b) of the coordinate plane. He is hurrying up to work so he wants to get out of his house as soon as possible. New app suggested n available Beru-taxi nearby. The i-th taxi is located at point (xi, yi) and moves with a speed vi.

Consider that each of n drivers will move directly to Vasiliy and with a maximum possible speed. Compute the minimum time when Vasiliy will get in any of Beru-taxi cars.

继续阅读

AIO2006 Solution

Fashion Statement

In the latest trend of skin-tight jeans and slimline handbags, having a bulging wallet or purse is simply a fashion crime. You are faced with a dilemma: either you find yourself disowned by your fashion-conscious friends, or risk carrying too little money for your taxi ride home.

You wish to carry the exact amount of money for your taxi ride (in case you are mugged or otherwise lose it). However, you also wish to use as few notes as possible to avoid being ridiculed by your friends. The notes available to you come in denominations of $1, $5, $20 and $100 (you never carry coins, which are simply far too bulky).

For example, if your taxi fare costs $67, the smallest number of notes you can carry is six — this is achieved by carrying three $20 notes, one $5 note and two $1 notes (20+20+20+5+1+1 = 67).

Your task is to determine the smallest number of notes you need to carry in order to make up a given taxi fare.

继续阅读

AIO2013 Solution(Chinese)

Archery

When you were young, you were awe-struck by the battle scene in The Lord of the Rings: The Two Towers. From then on, you were determined to become the greatest archer of all time. After years of training, you are finally at the International Archery Olympiad (IAO), in Auckland.

On each of the two days of the IAO, all contestants are given a score and ranked by that score. After the second day of competition, all contestants are given an overall score equal to the sum of their two scores and their overall rank is then calculated from this.

Katniss Legolas Link Merida Robin
Day 1 Score 50 70 20 40 0
Day 1 Rank 2 1 4 3 5
Day 2 Score 30 20 40 50 40
Day 2 Rank 4 5 2 1 2
Overall Score 80 90 60 90 40
Overall Rank 3 1 4 1 5

A contestant's rank is equal to the number of competitors with strictly greater scores than theirs, plus one. In the above example, there are two overall scores strictly greater than Katniss's, so her overall rank is (2+1)=3. There are no overall scores strictly greater than Legolas's, so his overall rank is (0+1)=1. (Notice that Legolas and Merida are both ranked 1, as no one has a strictly greater score than either of them.)

Sick with anticipation of the results, you sneak a look at a judge's laptop. The scores aren't shown, nor is your overall rank, but you do manage to glimpse your first-day rank and your second-day rank. You want to work out what your overall rank could be.

Your task is to write a program which, given the number of contestants in the IAO and your rank on each day, determines your best and worst possible overall rank.

继续阅读

[bzoj 1505][NOI2004]小H的小屋

Description

小H发誓要做21世纪最伟大的数学家。他认为,做数学家与做歌星一样,第一步要作好包装,不然本事再大也推不出去。为此他决定先在自己的住所上下功夫,让人一看就知道里面住着一个“未来的大数学家”。 为了描述方便,我们以向东为x轴正方向,向北为y轴正方向,建立平面直角坐标系。小H的小屋东西长为100Hil(Hil是小H自己使用的长度单位,至于怎样折合成“m”,谁也不知道)。东墙和西墙均平行于y轴,北墙和南墙分别是斜率为k1和k2的直线,k1和k2为正实数。北墙和南墙的墙角处有很多块草坪,每块草坪都是一个矩形,矩形的每条边都平行于坐标轴。相邻两块草坪的接触点恰好在墙上,接触点的横坐标被称为它所在墙的“分点”,这些分点必须是1到99的整数。 小H认为,对称与不对称性的结合才能充分体现“数学美”。因此,在北墙角要有m块草坪,在南墙角要有n块草坪,并约定m≤n。如果记北墙和南墙的分点集合分别为X1,X2,则应满足X1 X2,即北墙的任何一个分点一定是南墙的分点。 由于小H目前还没有丰厚的收入,他必须把草坪的造价降到最低,即草坪的占地总面积最小。你能编程帮他解决这个难题吗?

继续阅读

[bzoj 1096][ZJOI2007]仓库建设

Description

  L公司有N个工厂,由高到底分布在一座山上。如图所示,工厂1在山顶,工厂N在山脚。由于这座山处于高原内陆地区(干燥少雨),L公司一般把产品直接堆放在露天,以节省费用。突然有一天,L公司的总裁L先生接到气象部门的电话,被告知三天之后将有一场暴雨,于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同,在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件,在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓库的工厂,其产品应被运往其他的仓库进行储藏,而由于L公司产品的对外销售处设置在山脚的工厂N,故产品只能往山下运(即只能运往编号更大的工厂的仓库),当然运送产品也是需要费用的,假设一件产品运送1个单位距离的费用是1。假设建立的仓库容量都都是足够大的,可以容下所有的产品。你将得到以下数据:1:工厂i距离工厂1的距离Xi(其中X1=0);2:工厂i目前已有成品数量Pi;:3:在工厂i建立仓库的费用
Ci;请你帮助L公司寻找一个仓库建设的方案,使得总的费用(建造费用+运输费用)最小。

继续阅读