【BZOJ 4829】[HNOI2017] 队长快跑

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4829

解题报告

首先我们可以把每一条射线等价为一条垂直于$x$轴的射线
此时问题变成了$Flappy \ Bird$那样

然后我们发现问题就是上下两个凸包互相卡
然后用两个队列瞎搞搞就好了

另外这题精度巨坑
之前用$long double$各种判$EPS$还是挂成狗
所以建议安心用$long long$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000009;
const int LEN = 1e4;
const double PI = acos(-1);

int n,tot,st[N],head[2],tail[2];
struct Point{
	LL x,y; Point *nxt; int pt;
	inline Point() {}
	inline Point(LL a, LL b):x(a),y(b) {}
	inline Point operator + (const Point &P) {return Point(x + P.x, y + P.y);}
	inline Point operator - (const Point &P) {return Point(x - P.x, y - P.y);}
	inline Point operator * (double t) {return Point(x * t, y * t);}
	inline LL operator ^ (const Point &P) {return x * P.x + y * P.y;}
	inline LL operator * (const Point &P) {return x * P.y - y * P.x;}
	inline bool operator < (const Point &P) const {return x < P.x;}
	inline bool operator != (const Point &P) const {return x != P.x || y != P.y;}
	inline double len() {return sqrt(x * x + y * y);}
}ss,tt,p[N],vout[N],*que[2][N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline bool NotInRange(double div, double a, double b) {
	if (div >= -PI / 2 && div <= PI / 2) return (a < div || a > PI / 2) && (b < div || b > PI / 2);
	else if (div < 0) return a > div && a < PI / 2 && b > div && b < PI / 2;
	else return (a > div || a < PI / 2) && (b > div || b < PI / 2);
}

int main() {
	n = read(); tt.x = read(); tt.y = read();
	for (int i=1;i<=n;i++) {
		p[i].x = read(); p[i].y = read();
		double r1,r2,r3; scanf("%lf",&r1);
		r2 = atan2((ss-p[i]).y, (ss-p[i]).x);
		r3 = atan2((tt-p[i]).y, (tt-p[i]).x);
		if (NotInRange(r1, r2, r3)) p[i].pt = 1; //射线朝上 
		else p[i].pt = 0; //射线朝下 
	}
	sort(p+1, p+1+n);
	int lim = n; n = 0;
	for (int i=1;i<=lim;i++) {
		if (p[i].x < ss.x || tt.x < p[i].x) continue;
		p[++n] = p[i];
	} 
	p[++n] = tt; 
	que[0][tail[0] = head[0] = 1] = &ss; 
	que[1][tail[1] = head[1] = 1] = &ss;
	for (int i=1;i<=n;i++) {
		int &h1 = head[p[i].pt], &h2 = head[p[i].pt ^ 1], &t1 = tail[p[i].pt], &t2 = tail[p[i].pt ^ 1];
		Point **a1 = que[p[i].pt], **a2 = que[p[i].pt ^ 1];
		if (h2 < t2 && ((p[i] - *a2[h2]) * (*a2[h2 + 1] - *a2[h2])) * (p[i].pt==1? 1: -1) >= 0) {
			while (h2 < t2 && ((p[i] - *a2[h2]) * (*a2[h2 + 1] - *a2[h2])) * (p[i].pt==1? 1: -1) >= 0) {
				++h2;
			}
			p[i].nxt = a2[h2];
			a1[h1 = t1 = t1 + 1] = a2[h2];
		} else {
			while (h1 < t1 && ((p[i] - *a1[t1 - 1]) * (*a1[t1] - *a1[t1 - 1])) * (p[i].pt==1? 1: -1) >= 0) {
				--t1;
			}
			p[i].nxt = a1[t1];
		}
		a1[++t1] = &p[i];
	} 
	double ans = 0; 
	for (Point *cur=&p[n],*last;*cur!=ss;) {
		last = cur; cur = cur->nxt;
		ans += (*cur - *last).len(); 
	} 
	printf("%.10lf\n",ans);
	return 0;
}

240 thoughts to “【BZOJ 4829】[HNOI2017] 队长快跑”

  1. I every time used to read piece of writing in news papers but now as I am a user
    of internet therefore from now I am using net for articles
    or reviews, thanks to web.

  2. Whats up are using WordPress for your blog platform? I’m new to the blog world but I’m trying to get started and create my own. Do you require any html coding
    knowledge to make your own blog? Any help would be really appreciated!

  3. I got this web site from my buddy who informed me about this web
    site and now this time I am visiting this web site and reading
    very informative articles or reviews at this time.

  4. Pretty section of content. I just stumbled upon your
    website and in accession capital to assert that I acquire actually enjoyed account your blog posts.

    Any way I’ll be subscribing to your augment and even I achievement you access consistently rapidly.

  5. A motivating discussion is worth comment.
    There’s no doubt that that you ought to publish more about this subject matter,
    it might not be a taboo matter but typically people do not talk about such subjects.
    To the next! Best wishes!!

  6. I simply couldn’t go away your website before suggesting that I
    extremely loved the standard information an individual provide
    to your visitors? Is gonna be again continuously to inspect new
    posts

  7. Hey! I realize this is somewhat off-topic however I had to ask.

    Does managing a well-established blog like yours take a lot of
    work? I am completely new to blogging but I do write
    in my journal on a daily basis. I’d like to start a blog so I can share
    my personal experience and views online. Please let me know if you have any
    kind of recommendations or tips for brand new
    aspiring bloggers. Appreciate it!

  8. hello there and thank you for your info – I have definitely picked up
    anything new from right here. I did however expertise several technical issues using this site, as
    I experienced to reload the web site a lot of times previous to I could get
    it to load correctly. I had been wondering if your web
    host is OK? Not that I’m complaining, but sluggish loading instances times
    will sometimes affect your placement in google and can damage your quality score
    if ads and marketing with Adwords. Anyway I’m adding this RSS to my e-mail
    and can look out for a lot more of your respective fascinating
    content. Make sure you update this again soon.

  9. An interesting discussion is worth comment. I do
    believe that you need to write more on this subject matter,
    it may not be a taboo subject but generally
    people don’t talk about such topics. To the next!
    Many thanks!!

  10. My partner and I absolutely love your blog and find
    almost all of your post’s to be just what I’m looking for.
    Would you offer guest writers to write content for yourself?
    I wouldn’t mind creating a post or elaborating on a
    number of the subjects you write with regards to here.

    Again, awesome site!

  11. This design is spectacular! You most certainly know how to keep
    a reader amused. Between your wit and your videos, I was almost moved to
    start my own blog (well, almost…HaHa!) Wonderful job.
    I really loved what you had to say, and more than that,
    how you presented it. Too cool!

  12. I must thank you for the efforts you’ve put in writing this website.
    I’m hoping to see the same high-grade content from you later on as well.
    In fact, your creative writing abilities has inspired me to get my very own blog now 😉

  13. Magnificent goods from you, man. I’ve have in mind your stuff previous to and you are simply
    extremely excellent. I actually like what you’ve
    got here, certainly like what you’re stating and the way in which you say it.
    You are making it enjoyable and you continue to take care of to keep it sensible.
    I can not wait to read much more from you. That is actually a wonderful web
    site.

  14. My brother suggested I might like this web site. He
    was totally right. This post actually made my day. You can not imagine
    just how much time I had spent for this information!
    Thanks!

  15. Hey just wanted to give you a brief heads up and let you know a few of
    the images aren’t loading properly. I’m not sure why
    but I think its a linking issue. I’ve tried it in two
    different browsers and both show the same results.

  16. Its like you read my mind! You seem to know so much about this,
    like you wrote the book in it or something. I think that you
    can do with a few pics to drive the message home a little
    bit, but other than that, this is great blog.
    A great read. I’ll definitely be back. natalielise plenty of fish

  17. I feel that is among the so much important information for me.

    And i’m glad studying your article. But wanna statement on few general
    things, The web site style is perfect, the articles is in reality great : D.
    Good task, cheers

  18. Greetings from Los angeles! I’m bored at work so I decided to browse your site on my iphone
    during lunch break. I really like the information you present here
    and can’t wait to take a look when I get home. I’m amazed at how fast your blog loaded on my mobile ..
    I’m not even using WIFI, just 3G .. Anyhow, good site!

  19. I just couldn’t depart your web site before
    suggesting that I really loved the usual information an individual provide in your guests?

    Is going to be again regularly in order to check up on new posts

  20. Wonderful items from you, man. I have keep in mind your stuff previous to and you are simply too excellent.

    I actually like what you have bought right here, really like what you’re stating and the way in which during which you
    say it. You make it enjoyable and you still care for to stay it wise.
    I can not wait to read much more from you. This is really a wonderful web site.
    pof natalielise

  21. What you posted made a great deal of sense. But, consider this,
    suppose you were to create a killer headline? I
    am not saying your content is not solid., but suppose you added a post title that makes people want more?
    I mean 【BZOJ 4829】[HNOI2017] 队长快跑
    – Qizy's Database is a little plain. You could glance at Yahoo’s home page and see how they write article headlines to get viewers to click.
    You might add a video or a picture or two to grab readers interested
    about everything’ve written. Just my opinion, it would make your posts
    a little bit more interesting.

  22. Wonderful blog! I found it while searching on Yahoo News.
    Do you have any tips on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get there!
    Many thanks

  23. Someone necessarily assist to make significantly articles
    I might state. That is the very first time I frequented your
    website page and so far? I surprised with the research you made to create this
    particular put up incredible. Fantastic process!

  24. Hi! I could have sworn I’ve been to this website before but after reading through some of the post I realized it’s new to me.
    Anyhow, I’m definitely delighted I found it and I’ll
    be book-marking and checking back often!

  25. Hi! This is my 1st comment here so I just wanted to give a quick shout
    out and tell you I really enjoy reading your posts.
    Can you suggest any other blogs/websites/forums that cover the same subjects?
    Thanks a ton!

  26. I’d like to thank you for the efforts you have put in penning this site.
    I’m hoping to view the same high-grade content by you in the future as
    well. In truth, your creative writing abilities has inspired me to get my very own site now 😉

  27. hello there and thank you for your info – I
    have definitely picked up something new from right here. I did however expertise some technical
    issues using this website, since I experienced to reload the site a lot of times
    previous to I could get it to load correctly. I had been wondering if your hosting is OK?
    Not that I am complaining, but slow loading instances times will very frequently affect your placement in google and could damage your high quality score if advertising and marketing with Adwords.

    Anyway I am adding this RSS to my email and could look out
    for much more of your respective interesting content.

    Make sure you update this again soon.

  28. I believe that is one of the such a lot important info for me.
    And i am satisfied studying your article. However wanna commentary on some normal things, The web site style is
    great, the articles is truly nice : D. Good task,
    cheers

  29. I know this if off topic but I’m looking into starting my own blog and was wondering what all is needed to get
    set up? I’m assuming having a blog like yours would cost a pretty penny?
    I’m not very web smart so I’m not 100% sure.
    Any recommendations or advice would be greatly appreciated.
    Kudos

  30. Heya outstanding blog! Does running a blog similar to this require a massive amount work?
    I have virtually no expertise in computer programming however I
    was hoping to start my own blog in the near future.
    Anyway, if you have any ideas or tips for new blog owners please share.
    I know this is off topic but I just needed to ask. Kudos!

  31. I’m amazed, I must say. Seldom do I come across a blog that’s both equally educative and engaging, and let me tell
    you, you have hit the nail on the head. The issue is something that not enough men and women are speaking intelligently about.
    Now i’m very happy that I found this in my hunt for something regarding this.

  32. I loved as much as you will receive carried out right here.

    The sketch is tasteful, your authored subject matter stylish.

    nonetheless, you command get got an edginess over that you wish be delivering the following.
    unwell unquestionably come more formerly again as exactly
    the same nearly very often inside case you shield
    this increase.

  33. Great post. I was checking constantly this blog and I’m impressed!

    Very useful info particularly the last section 🙂 I deal with
    such information much. I was seeking this particular info for a long time.
    Thanks and best of luck.

  34. Hi I am so happy I found your website, I really found you
    by error, while I was researching on Yahoo for something else,
    Regardless I am here now and would just like to say cheers for a marvelous post and a all round entertaining blog
    (I also love the theme/design), I don’t have time to go through
    it all at the minute but I have saved it and also added in your RSS feeds, so when I have time I will be back to
    read more, Please do keep up the excellent job.

  35. Hi, i read your blog from time to time and i own a similar one and
    i was just wondering if you get a lot of spam comments?
    If so how do you stop it, any plugin or anything you can advise?
    I get so much lately it’s driving me insane so any support
    is very much appreciated.

  36. I am really enjoying the theme/design of your blog. Do you ever run into
    any internet browser compatibility issues? A number of my blog audience have complained about my website not
    operating correctly in Explorer but looks great in Opera.
    Do you have any advice to help fix this issue?

  37. I don’t even know how I ended up here, but I thought this post was
    great. I don’t know who you are but definitely you’re going to a
    famous blogger if you aren’t already 😉 Cheers!

  38. Hello, i feel that i saw you visited my weblog so i
    got here to go back the want?.I’m attempting to in finding issues to enhance my
    web site!I assume its ok to make use of a few of your concepts!!

  39. I do believe all the ideas you’ve offered on your post.
    They’re really convincing and can certainly work.

    Still, the posts are very brief for novices. Could you please prolong them a
    bit from subsequent time? Thank you for the post.

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

    But he’s tryiong none the less. I’ve been using WordPress on a number of websites
    for about a year and am worried about switching to
    another platform. I have heard good things about blogengine.net.

    Is there a way I can import all my wordpress content into it?
    Any kind of help would be really appreciated!

  41. Do you have a spam issue on this site; I also am a blogger, and I
    was wanting to know your situation; we have developed some nice methods and we are looking to trade strategies with other
    folks, why not shoot me an e-mail if interested.

  42. Having read this I thought it was rather enlightening.
    I appreciate you taking the time and effort to put
    this informative article together. I once again find myself
    personally spending a lot of time both reading and commenting.
    But so what, it was still worth it!

  43. Its such as you learn my thoughts! You seem to understand so much approximately this, such as you wrote the e-book in it or something.

    I feel that you just can do with a few % to pressure the message house a bit, however instead of
    that, this is excellent blog. A great read. I’ll definitely be back.

  44. I was suggested this web site by my cousin. I am not sure whether this post is written by
    him as nobody else know such detailed about my trouble.

    You’re amazing! Thanks!

  45. Hey would you mind stating which blog platform you’re working with?
    I’m looking to start my own blog soon but I’m having a difficult time choosing
    between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design and style seems different then most blogs and I’m
    looking for something completely unique. P.S Sorry
    for getting off-topic but I had to ask!

  46. Great blog here! Also your site loads up fast!
    What host are you using? Can I get your affiliate link to your
    host? I wish my website loaded up as fast as yours lol

  47. You are so cool! I don’t think I have read
    anything like that before. So good to discover someone with genuine thoughts
    on this topic. Really.. thank you for starting this up.
    This website is something that’s needed on the web, someone with a little originality!

  48. Having read this I thought it was extremely informative. I appreciate you spending some time and effort to put
    this short article together. I once again find myself spending a lot of time
    both reading and posting comments. But so what, it was still worth it!

  49. I’m extremely impressed with your writing skills and also
    with the layout on your weblog. Is this a paid theme or did you modify it yourself?
    Either way keep up the nice quality writing, it’s rare to see a great blog like this one nowadays.

  50. I got this site from my pal who informed me about this web site and at the moment this
    time I am visiting this web site and reading very informative articles at this place.

  51. Hello There. I discovered your weblog the usage of msn. This is an extremely neatly written article.
    I will make sure to bookmark it and come back to learn extra of your helpful info.
    Thank you for the post. I will definitely comeback.

  52. Good day! Would you mind if I share your blog
    with my zynga group? There’s a lot of folks that I think would really enjoy your content.

    Please let me know. Many thanks

  53. You actually make it appear really easy along with your presentation but I in finding this
    matter to be really something that I feel I’d never understand.
    It sort of feels too complex and extremely broad for me.

    I’m taking a look ahead to your next put up,
    I will try to get the hold of it!

  54. It’s remarkable to go to see this web page and reading the views of all mates on the topic of this article,
    while I am also eager of getting experience.

  55. This design is spectacular! You certainly know how to keep a reader amused. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Excellent job. I really loved what you had to say, and more than that, how you presented it. Too cool!

Leave a Reply to mojang minecraft download Cancel reply

Your email address will not be published. Required fields are marked *