1
13
2013
37

USACO 5.1

1.Fencing the Cows

二维凸包(Convex Hulls)问题。

以下是usaco training上的教程:

  • Find a point which will be within the convex hull:【注1】
  • Calculate the angle that each point makes with the x axis (within the range 0 to 360 degrees)【注2】
  • Sort the points based on this angle
  • Add the first two points
  • For every other point except the last point
  • Make it the next point in the convex hull
  • Check to see if the angle it forms with the previous two points is greater than 180 degrees. As long as the angle formed with the last two points is greater than 180 degrees, remove the previous point【注3】
  • To add the last point
  • Perform the deletion above,
  • Check to see if the angle the last point forms with the previous point and the first point is greater than 180 degrees or if the angle formed with the last point and the first two points is greater than 180 degrees.【注4】
  • If the first case is true, remove the last point, and continue checking with the next-to-last point.
  • If the second case is true, remove the first point and continue checking.
  • Stop when neither case is true.
  • The adding of the points is linear time, as is the calculation of the angles. Thus, the run-time is dominated by the time of the sort, so gift-wrapping runs in O(nlogn) time, which is provably optimal.

【注1】:

计算点集的中点(可以简单地取所有点在x和y方向上的均值)。此点必在凸包内。

【注2】:

计算各个点与中点的连线与x轴的夹角(在0到2pi之间),这个可以使用C语言math.h库函数中的atan2(double y,double x)来实现,不过注意atan2的值域是(-pi,pi],需要进一步将其映射到[0,2pi)区间内。此外注意atan2(0,0)==0,所以我们可以放心地将其应用到中点和点集中某点重合的情况。

【注3】:

检查逆时针连续的三点是否形成“右转”的角,如果“右转”就把“转角”的点删除,否则会出现一个凹多边形。注意删除一个“转角”之后还要要不断检查之前的点,直到该删除的点全部删除为止。

【注4】:

到此为止从第一个点逆时针转到最后一个点的所有“转角”都成为左转的角了,但是当我们把最后一个点和第一个点相连时,这两个点处的“转角”还可能是“右转”的。为了排除这种情况我们要不断检查第一个和最后一个点,如果“右转”就删除,直到它们全部“左转”为止。


怎样判断是否“右转”:

设有逆时针方向连续的三点(x1,y1),(x2,y2),(x3,y3),首先取两向量<x2-x1,y2-y1>(记为<p1,q1>)和<x3-x2,y3-y2>(记为<p2,q2>),当两向量的向量积的z分量小于0时(即p1q2-p2q1<0)就形成了所谓的“右转”关系。


2.Starry Night

可以简单地应用floodfill来找出所有星座。比较星座是否相同时有些麻烦,因为涉及到平移、旋转、翻转等操作,我是通过修改比对星座时的遍历顺序来实现的,这样最多一共需要比对八种遍历方式下两星座图是否重合。


3.Musical Themes

用一个时间复杂度是O(L*N2)的算法过了。其中N是音符的数量,L是需要比对的Themes的平均长度,由于这个L难以预料,所以多少有点侥幸。思路如下:

用dp[i]表示前i个音符中themes的最大长度,用note数组表示所有的音符,则有

dp[i]={

    dp[i-1]+1(if note[i-dp[i-1]]...note[i]这个序列或其变调形式

              可以在note[0]...note[i-dp[i-1]-1]范围内找到);

    dp[i-1](if not)

}

注意dp[i]比dp[i-1]大1当且仅当note[i]加入后可以与前dp[i-1]个音符形成一个新theme。


usaco的官方题解给出了一个O(N2)的算法,更充分地利用了每一步的计算结果:

Let theme(i,j) be the length of the longest theme which occurs starting at both note i and j. 

Note that if note[i+1]-note[i]==note[j+1]-note[j], than theme(i,j)=1+theme(i+1,j+1). Otherwise, theme(i,j)=1.

Thus, we order the search in such a way that theme(i,j) is tested immediately after theme(i+1,j+1), keeping track of the length of the current theme, as well as the length of the longest theme found so far.

#include <fstream.h>

int     n;
int     note[5000];

int 
main () {
    ifstream filein ("theme.in");
    filein >> n;
    for (int i = 0; i < n; ++i) 
	filein >> note[i];
    filein.close ();

    int     longest = 1;

    for (int i = 1; i < n; ++i) {
	int     length = 1;
	for (int j = n - i - 1 - 1; j >= 0; --j) {
	    if (note[j] - note[j + 1] == note[j + i] - note[j + i + 1]) {
		++length;
		if (length > i) 
		    length = i;
		if (longest < length)
		    longest = length;
	    }
	    else {
		length = 1;
	    }
	}
    }

    ofstream fileout ("theme.out");
    fileout << ((longest >= 5) ? longest : 0) << endl;
    fileout.close ();

    exit (0);
}
Category: USACO | Tags: usaco 凸包 convex hulls | Read Count: 1704
pay for dissertation 说:
2019年10月08日 12:43

Wow! I’m browsing away perusing your web journal from my lap! Simply needed to say I adore perusing your website and anticipate every one of your posts! Carry on the eminent work.Feel free to browse for getting more information about writing work

seo service london 说:
2024年1月16日 07:33

It is a completely interesting blog publish.I often visit your posts for my project's help about Diwali Bumper Lottery and your super writing capabilities genuinely go away me taken aback

비행기도메인 说:
2024年1月29日 07:12

My programmer is trying to persuade me to move to .net from PHP. I have always disliked the idea because of

키톤 가입코드 说:
2024年1月29日 07:20

It's which means that amazing together with inspiring. We really enjoy any designs together with whoever should get it all during the post shall be grinning.

안전놀이터순위 说:
2024年1月29日 07:29

your active wear brand:Your style, your rule, Rhone brings your favorite and most quality active wear designed by keeping you in mind, our performance driven clothing is lightweight, style and with rhone coupons code affordable for everyone .

파워볼최상위사이트 说:
2024年1月29日 07:34

extraordinarily excellent article, i liked perusing your publish, especially respectable percentage, i need to twit this to my adherents. A good deal preferred! Effortlessly, the object is truly the first-rate topic in this registry associated difficulty. I in shape in together with your conclusions and will eagerly sit up for your next updates. 

키노사다리작업 说:
2024年1月29日 07:40

extraordinarily excellent article, i liked perusing your publish, especially respectable percentage, i need to twit this to my adherents. A good deal preferred! Effortlessly, the object is truly the first-rate topic in this registry associated difficulty. I in shape in together with your conclusions and will eagerly sit up for your next updates. 

검증나라 说:
2024年1月29日 07:50

An impressive share! I have just forwarded this onto a colleague who was doing a

메이저놀이터모음 说:
2024年1月29日 08:00

That is the excellent mindset, nonetheless is just not help to make every sence whatsoever preaching about that mather. Virtually any method many thanks in addition to i had endeavor to promote your own article in to delicius nevertheless it is apparently a dilemma using your information sites can you please recheck the idea. thanks once more

사설토토 说:
2024年1月29日 08:06

I have a similar interest this is my page read everything carefully and let me know what you think.

먹튀검증커뮤니티 说:
2024年1月29日 08:10

youre so cool! I dont thinkply made the excellent factor. You clearly know what youre talking about, and i can truly get behind that. Thanks for being so prematurely and so honest.

토토사이트 说:
2024年1月29日 08:16

youre so cool! I dont thinkply made the excellent factor. You clearly know what youre talking about, and i can truly get behind that. Thanks for being so prematurely and so honest.

토토사이트추천 说:
2024年1月29日 08:26

My programmer is trying to persuade me to move to .net from PHP. I have always disliked the idea because of

먹튀신고 说:
2024年1月29日 08:45

It's which means that amazing together with inspiring. We really enjoy any designs together with whoever should get it all during the post shall be grinning.

소울 카지노 说:
2024年1月29日 08:52

your active wear brand:Your style, your rule, Rhone brings your favorite and most quality active wear designed by keeping you in mind, our performance driven clothing is lightweight, style and with rhone coupons code affordable for everyone .

스포츠 중계 说:
2024年1月29日 08:57

extraordinarily excellent article, i liked perusing your publish, especially respectable percentage, i need to twit this to my adherents. A good deal preferred! Effortlessly, the object is truly the first-rate topic in this registry associated difficulty. I in shape in together with your conclusions and will eagerly sit up for your next updates. 

먹튀검증 说:
2024年1月29日 09:04

extraordinarily excellent article, i liked perusing your publish, especially respectable percentage, i need to twit this to my adherents. A good deal preferred! Effortlessly, the object is truly the first-rate topic in this registry associated difficulty. I in shape in together with your conclusions and will eagerly sit up for your next updates. 

메이저사이트 说:
2024年1月29日 09:17

An impressive share! I have just forwarded this onto a colleague who was doing a

먹튀검증사이트 说:
2024年1月29日 09:24

That is the excellent mindset, nonetheless is just not help to make every sence whatsoever preaching about that mather. Virtually any method many thanks in addition to i had endeavor to promote your own article in to delicius nevertheless it is apparently a dilemma using your information sites can you please recheck the idea. thanks once more

파라오카지노주소 说:
2024年1月29日 09:30

I have a similar interest this is my page read everything carefully and let me know what you think.

먹튀검증커뮤니티 说:
2024年1月29日 09:34

youre so cool! I dont thinkply made the excellent factor. You clearly know what youre talking about, and i can truly get behind that. Thanks for being so prematurely and so honest.

메이저안전놀이터 说:
2024年1月29日 09:38

youre so cool! I dont thinkply made the excellent factor. You clearly know what youre talking about, and i can truly get behind that. Thanks for being so prematurely and so honest.

토토사이트추천 说:
2024年1月29日 09:48

They can be tips related to numerous composition categories, including college applications and complex assignments like Kaplan assignment help

토토사이트추천 说:
2024年1月29日 09:54

Japandi style is a blend of Japanese and Scandinavian design principles. It is characterized by simple, clean lines and a focus on natural materials. Japandi furniture is often made of wood or bamboo, and the spaces are designed to be open and airy. This style is also known for its use of muted colors, which create a calming atmosphere. In recent years, Japandi has become increasingly popular as people seek to create a more serene and orderly space in their homes. If you are looking to add a touch of Japandi to your own home, start by incorporating some key elements into your design. Look for furniture with clean lines and natural materials, and use light colors to create a sense of calm. You can also add personal touches such as Japanese art or pottery to further reflect the Japandi aesthetic.

안전놀이터가입 说:
2024年1月29日 09:59

These you will then see the most important thing, the application provides you a website a powerful important internet page:

먹튀사이트 说:
2024年1月29日 10:02

This was really an interesting topic and I kinda agree with what you have mentioned here!Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subject

먹튀검증사이트 说:
2024年1月29日 10:06

This was really an interesting topic and I kinda agree with what you have mentioned here!Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subject

먹튀검증 说:
2024年1月29日 10:41

They can be tips related to numerous composition categories, including college applications and complex assignments like Kaplan assignment help

주간토토 说:
2024年1月29日 10:48

Hi! This is my first visit to your blog! We are a team of volunteers and new initiatives in the same niche. Blog gave us useful information to work. You have done an amazing job

안전놀이터가입 说:
2024年1月29日 10:55

Japandi style is a blend of Japanese and Scandinavian design principles. It is characterized by simple, clean lines and a focus on natural materials. Japandi furniture is often made of wood or bamboo, and the spaces are designed to be open and airy. This style is also known for its use of muted colors, which create a calming atmosphere. In recent years, Japandi has become increasingly popular as people seek to create a more serene and orderly space in their homes. If you are looking to add a touch of Japandi to your own home, start by incorporating some key elements into your design. Look for furniture with clean lines and natural materials, and use light colors to create a sense of calm. You can also add personal touches such as Japanese art or pottery to further reflect the Japandi aesthetic.

먹튀검증 说:
2024年1月29日 11:00

This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. best food truck in lincoln ne

먹튀검증 说:
2024年1月29日 11:08

This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. best food truck in lincoln ne

퍼스트카지노쿠폰 说:
2024年1月29日 11:18

Voice technology, such as smart speakers and virtual assistants, has become increasingly popular with consumers as a way to access media content and control smart home devices.

클레오카지노쿠폰 说:
2024年1月29日 11:26

technologies is creating a new integrated supply chain for the production and delivery of multimedia and information content Most of the employment related to e-commerce around the content industries and communication infrastructure such as the Internet.

국내 온라인카지노 说:
2024年1月29日 11:32

For the most accurate and up-to-date information, I recommend checking the latest online sources or contacting the relevant entity directly.

คาสิโน 说:
2024年1月29日 11:37

Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better. The post is written in very a good manner and it contains many useful information for me. Thank you very much and will look for more postings from you.

먹튀사이트 说:
2024年1月29日 11:44

Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better. The post is written in very a good manner and it contains many useful information for me. Thank you very much and will look for more postings from you.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com