【BZOJ 1137】[POI2009] Wsp 岛屿

相关链接

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

解题报告

不难发现每一个点应尽量向编号大的点连边
所以就只剩下$O(n)$条线段了,直接做半平面交就好

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100009;
const double EPS = 1e-6;
 
int n, m, tot;
vector<int> del[N];
struct Point{
    double x, y;
    inline Point() {
    }
    inline Point(double _x, double _y):x(_x), y(_y) {
    }
    inline Point operator - (const Point &P) const {
        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 d) {
        return Point(x * d, y * d);
    }
    inline double operator * (const Point &P) {
        return x * P.y - y * P.x;
    }
    inline double len() {
        return sqrt(x * x + y * y);
    }
}p[N];
struct Line{
    Point a, b;
    double slope;
    inline Line() {
    }
    inline Line(const Point &_a, const Point &_b):a(_a), b(_b) {
    }
    inline bool operator < (const Line &L) const {
        return slope < L.slope;
    }
    inline Point intersect(const Line &L) {
        double s1 = (L.b - L.a) * (b - L.a);
        double s2 = (a - L.a) * (L.b - L.a);
        return a + (b - a) * (s2 / (s1 + s2));
    }
    inline bool OnLeft(const Point &P) {
        return (b - a) * (P - a) > EPS;
    }
}l[N];
 
inline int read() {
    char c = getchar(); int ret = 0, f = 1;
    for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
    for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
    return ret * f;
}
 
inline void HalfPlaneIntersection(Line *arr, int &sz) {
    for (int i = 1; i <= sz; i++) {
        Point vec = arr[i].b - arr[i].a;
        arr[i].slope = atan2(vec.y, vec.x);
    }
    sort(arr + 1, arr + 1 + sz);
    int l = 1, r = 0;
    for (int i = 1; i <= sz; i++) {
        for (; l < r && !arr[i].OnLeft(arr[r].intersect(arr[r - 1])); r--); 
        for (; l < r && !arr[i].OnLeft(arr[l].intersect(arr[l + 1])); l++);
        arr[++r] = arr[i];
    }
    for (; l < r - 1 && !arr[l].OnLeft(arr[r].intersect(arr[r - 1])); r--);
    sz = 0;
    for (int i = l; i <= r; i++) {
        arr[++sz] = arr[i];
    }
    arr[0] = arr[sz];
    arr[sz + 1] = arr[1];
}
 
int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; i++) {
        p[i].x = read();
        p[i].y = read();
    }
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        del[min(x, y)].push_back(max(x, y));
    }
    for (int i = 1; i < n; i++) {
        sort(del[i].begin(), del[i].end());
        int to = n;
        while (!del[i].empty() && *--del[i].end() == to) {
            to--;
            del[i].pop_back();
        }
        if (i == 1 && to == n) {
            printf("%.10lf", (p[1] - p[n]).len());
            exit(0);
        }
        if (to > i) {
            l[++tot] = Line(p[to], p[i]);
        }
    }
    l[++tot] = Line(p[1], p[n]); 
    HalfPlaneIntersection(l, tot);
    double ans = -(p[1] - p[n]).len();
    Point last = l[1].intersect(l[0]);
    for (int i = 1; i <= tot; i++) {
        Point cur = l[i].intersect(l[i + 1]);
        ans += (cur - last).len();
        last = cur;
    }
    printf("%.10lf\n", ans);
    return 0;
}

217 thoughts to “【BZOJ 1137】[POI2009] Wsp 岛屿”

  1. Hmm is anyone else having problems with the images
    on this blog loading? I’m trying to figure out if its a problem on my end or if it’s the blog.
    Any suggestions would be greatly appreciated.

  2. Nice post. I was checking constantly this blog and I
    am impressed! Very useful info specifically the last
    part 🙂 I care for such info a lot. I was
    seeking this certain information for a very long time.
    Thank you and good luck.

  3. I just couldn’t leave your website before suggesting that I extremely loved the usual information a person provide to your visitors?
    Is gonna be back often to check up on new posts

  4. It’s a shame you don’t have a donate button! I’d certainly donate to this fantastic blog!

    I guess for now i’ll settle for bookmarking and adding
    your RSS feed to my Google account. I look forward to new updates and will
    share this blog with my Facebook group. Chat soon!

  5. Good post however I was wanting to know if you could write a litte more on this topic?
    I’d be very grateful if you could elaborate a little bit further.
    Cheers!

  6. An intriguing discussion is definitely worth comment. I do think
    that you need to write more on this subject matter, it might not be a taboo matter but generally people don’t speak about these issues.
    To the next! Many thanks!!

  7. Woah! I’m really digging the template/theme of this blog.
    It’s simple, yet effective. A lot of times it’s difficult to get
    that “perfect balance” between superb usability and appearance.
    I must say you’ve done a excellent job with this.
    In addition, the blog loads very quick for me on Safari.
    Superb Blog!

  8. Magnificent beat ! I would like to apprentice at the same time as
    you amend your website, how could i subscribe for a weblog site?
    The account aided me a acceptable deal. I were tiny bit familiar of this your broadcast offered
    vibrant transparent idea

  9. you’re in reality a good webmaster. The website loading speed
    is incredible. It kind of feels that you’re doing any distinctive trick.
    Also, The contents are masterwork. you’ve performed a magnificent activity
    on this matter!

  10. I’ve been browsing online more than 2 hours today, yet I never found
    any interesting article like yours. It is pretty worth
    enough for me. Personally, if all webmasters
    and bloggers made good content as you did,
    the web will be a lot more useful than ever before.

  11. Please let me know if you’re looking for a article writer for your blog.

    You have some really great articles and I think I would be a good asset.
    If you ever want to take some of the load off, I’d really like to write some content
    for your blog in exchange for a link back to mine. Please send me an email if interested.
    Many thanks! natalielise plenty of fish

  12. Hi would you mind sharing which blog platform you’re working with?
    I’m planning to start my own blog in the near future but I’m having a difficult time deciding
    between BlogEngine/Wordpress/B2evolution and
    Drupal. The reason I ask is because your layout seems different then most blogs
    and I’m looking for something unique. P.S Apologies for
    being off-topic but I had to ask!

  13. Excellent post. Keep writing such kind of information on your page.
    Im really impressed by your blog.
    Hi there, You’ve performed an incredible job. I will certainly digg it and in my view suggest to my
    friends. I’m confident they will be benefited from this web site.

  14. What’s Happening i’m new to this, I stumbled upon this I’ve discovered It absolutely helpful and it has helped me out loads.
    I hope to give a contribution & assist other customers like its
    aided me. Good job.

  15. That is a very good tip particularly to those new to the blogosphere.
    Brief but very precise information… Many thanks for sharing this one.
    A must read post!

  16. You actually make it seem so easy with your presentation but I find this
    topic to be actually something which I think I would never understand.
    It seems too complicated and very broad for me. I’m looking forward for your next post, I’ll try to get the hang of it!

  17. With havin so much written content do you ever run into any issues of
    plagorism or copyright violation? My blog has a lot of exclusive content I’ve either authored myself or outsourced but it
    appears a lot of it is popping it up all over the web without my permission.
    Do you know any methods to help prevent content
    from being ripped off? I’d truly appreciate it.

  18. When I initially commented I seem to have clicked on the -Notify me when new comments are added- checkbox
    and now whenever a comment is added I get 4 emails with the
    same comment. There has to be an easy method you can remove me from that service?

    Kudos!

  19. I simply couldn’t leave your site before suggesting that I actually
    loved the usual info a person supply for your
    visitors? Is going to be back continuously in order to check out
    new posts

  20. I just like the helpful information you supply for your articles.
    I’ll bookmark your blog and check once more right here
    frequently. I am reasonably certain I’ll learn lots of new stuff proper right here!
    Good luck for the following!

  21. Having read this I thought it was very informative.

    I appreciate you spending some time and energy to put this information together.
    I once again find myself personally spending way
    too much time both reading and commenting.
    But so what, it was still worthwhile!

  22. Hello, I think your website could possibly be having web browser compatibility problems.
    Whenever I look at your web site in Safari, it looks
    fine but when opening in I.E., it has some overlapping issues.
    I simply wanted to give you a quick heads up!
    Besides that, wonderful site!

  23. I got this website from my buddy who told me on the topic
    of this website and now this time I am visiting this
    web page and reading very informative posts at this
    place.

  24. Heya i am for the first time here. I found this board and
    I find It truly useful & it helped me out much. I hope to give something back
    and aid others like you helped me.

  25. Pretty component to content. I just stumbled upon your blog and in accession capital to claim that I get in fact enjoyed account your blog posts.
    Anyway I will be subscribing on your augment or even I success you
    access persistently rapidly.

  26. I have been browsing online greater than 3 hours lately,
    but I never discovered any attention-grabbing article like yours.
    It is pretty worth sufficient for me. Personally,
    if all web owners and bloggers made good content material
    as you probably did, the net will probably
    be a lot more helpful than ever before.

  27. Having read this I thought it was very informative.

    I appreciate you spending some time and effort to put this short article together.

    I once again find myself personally spending a significant amount of time both reading and leaving comments.
    But so what, it was still worth it!

  28. Hello are using WordPress for your site 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 greatly appreciated!|

  29. How many would you like? mmhealthguide.com Durant, who was selected with the second overall pick in the 2007 draft, just completed his sixth season in the NBA. The 24-year-old forward averaged 28.1 points, 7.9 rebounds and 4.6 assists last season.

  30. hello!,I like your writing very much! percentage we keep up a correspondence more about your post on AOL? I need an expert in this area to resolve my problem. Maybe that is you! Looking ahead to peer you.

  31. There’s a three month trial period nootropil online kaufen Cable companies have become hot assets as their cable lines, designed to deliver TV to homes, have been upgraded to carry voice calls and Internet at speeds often five times faster than competing services from telecom operators and they have been snatching customers from them.

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

  33. Hey there. I found your site by way of Google even as searching for a comparable matter, your web site got here up. It appears to be good. I have bookmarked it in my google bookmarks to visit then.

  34. Howdy very cool website!! Man .. Beautiful .. Wonderful .. I’ll bookmark your website and take the feeds also…I am satisfied to find numerous helpful information right here within the post, we’d like develop extra techniques on this regard, thanks for sharing.

  35. I just want to mention I’m beginner to weblog and truly loved your web page. More than likely I’m planning to bookmark your site . You absolutely come with outstanding posts. Thanks a bunch for revealing your web page.

  36. I’ve learned several important things by means of your post. I will also like to say that there can be situation in which you will apply for a loan and do not need a cosigner such as a Fed Student Support Loan. In case you are getting a loan through a regular banker then you need to be prepared to have a cosigner ready to allow you to. The lenders will probably base any decision on the few factors but the most significant will be your credit ratings. There are some lenders that will likewise look at your work history and come to a decision based on that but in most cases it will hinge on your report.

  37. Right here is the right webpage for everyone who hopes to understand this topic.

    You understand so much its almost tough to argue with you (not
    that I actually will need to…HaHa). You definitely put a new spin on a topic that’s
    been written about for many years. Wonderful stuff, just excellent!

  38. parcel forwarding service, Amazon, international package delivery service from the UK , international courier from UK, international package delivery, global parcel shipping, delivery service from the UK, UK package transport solution, delivery service, shipping solution

  39. Hiya, I am really glad I have found this information. Nowadays bloggers publish only about gossip and internet stuff and this is actually frustrating. A good site with exciting content, that is what I need. Thank you for making this web site, and I’ll be visiting again. Do you do newsletters by email?

  40. Greetings! I know this is kinda off topic however I’d figured I’d ask.
    Would you be interested in trading links or maybe guest writing a blog article or vice-versa?
    My blog addresses a lot of the same subjects as yours and I think we could greatly benefit from each
    other. If you happen to be interested feel free to shoot
    me an email. I look forward to hearing from you!
    Superb blog by the way!

  41. Link exchange is nothing else but it is just placing the other person’s blog link on your page at appropriate place and other person will also
    do similar in favor of you.

  42. Greetings from Los angeles! I’m bored to tears at work
    so I decided to check out your site on my iphone during lunch break.
    I enjoy the information you present here and can’t wait to
    take a look when I get home. I’m shocked at how fast your blog loaded on my mobile ..
    I’m not even using WIFI, just 3G .. Anyways, great
    site!

  43. I do some voluntary work waar kan ik viagra kopen in amsterdam Now is not a great time to have a phobia of sharks. Between Syfy’s «Sharknado,» Discovery Channel’s Shark Week and the occasional shark sighting on the New York subway, these infamous creatures of the deep are more popular than ever. As Syfy continues to feed the shark frenzy with another TV movie, «Ghost Shark,» on August 22, we take a look back at the best and baddest sharks in pop culture.

  44. Hello there. I discovered your blog by way of Google whilst searching for a related matter, your web site came up. It appears to be great. I have bookmarked it in my google bookmarks to visit then.

  45. It’а†s in reality a nice and useful piece of info. I am glad that you just shared this useful info with us. Please stay us up to date like this. Thank you for sharing.

  46. I used to be recommended this web site by way of my cousin. I’m no longer sure
    whether this put up is written through him as no one else recognize such certain about my trouble.
    You are amazing! Thanks!

  47. Greate article. Keep posting such kind of info on your site.
    Im really impressed by it.
    Hi there, You’ve performed an excellent job.
    I will definitely digg it and in my view suggest
    to my friends. I’m confident they’ll be benefited
    from this site.

  48. Simply want to say your article is as surprising. The clarity on your post is simply spectacular and that i could suppose you are knowledgeable on this
    subject. Fine together with your permission let me to
    grasp your RSS feed to keep updated with impending post. Thanks a million and please keep up
    the enjoyable work.

  49. I’m not sure the place you’re getting your information, however great topic.
    I must spend some time studying much more or working out more.
    Thank you for magnificent info I was on the lookout for this information for my mission.

  50. You could certainly see your enthusiasm within the
    work you write. The arena hopes for more passionate writers like you who aren’t afraid to say how they believe.
    Always follow your heart.

  51. you’re in point of fact a just right webmaster.
    The website loading velocity is amazing. It kind of feels that
    you’re doing any distinctive trick. Moreover,
    The contents are masterwork. you have performed a excellent task in this matter!

  52. Hey! Do you know if they make any plugins to help with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good
    gains. If you know of any please share. Thank you!

  53. I have been exploring for a little bit for any high-quality articles or weblog posts in this sort of area .

    Exploring in Yahoo I ultimately stumbled upon this website.
    Studying this information So i’m satisfied to show that I’ve an incredibly just right uncanny feeling I found out just what I needed.
    I such a lot undoubtedly will make certain to don?t forget this website and give
    it a glance regularly.

  54. An outstanding share! I’ve just forwarded this onto a co-worker who has been conducting a little
    research on this. And he in fact bought me lunch due to the fact
    that I found it for him… lol. So allow me to reword this….
    Thank YOU for the meal!! But yeah, thanks for spending time to
    discuss this matter here on your internet site.

  55. You could certainly see your enthusiasm in the work you write. The world hopes for even more passionate writers like you who are not afraid to say how they believe. Always follow your heart.

  56. Your style is so unique compared to other folks I have read stuff from.
    Thank you for posting when you’ve got the opportunity, Guess I will
    just book mark this web site.

  57. I got what you mean , appreciate it for posting .Woh I am thankful to find this website through google. “Those who corrupt the public mind are just as evil as those who steal from the public.” by Theodor Wiesengrund Adorno.

  58. Good article and straight to the point. I don’t know if this is truly the best place to ask but do you folks have any thoughts on where to employ some professional writers? Thanks 🙂

  59. I feel that is one of the most significant information for me.
    And i am satisfied reading your article. But should commentary on few common things, The web site
    taste is perfect, the articles is really excellent : D.
    Good job, cheers

  60. Hi! This post couldn’t be written any better!
    Reading this post reminds me of my previous room mate!

    He always kept talking about this. I will forward this write-up to him.

    Pretty sure he will have a good read. Many thanks for sharing!

  61. I definitely wanted to make a small word to be able to express gratitude to you for these precious techniques you are sharing on this site. My extended internet lookup has finally been honored with awesome concept to go over with my contacts. I ‘d mention that we readers actually are very much blessed to exist in a useful network with very many marvellous people with great advice. I feel quite grateful to have used your web pages and look forward to so many more brilliant moments reading here. Thanks once more for a lot of things.

  62. You really make it seem so easy with your presentation but I find this topic to be actually something which I think I would never understand. It seems too complicated and very broad for me. I am looking forward for your next post, I will try to get the hang of it!|

  63. Your style is so unique in comparison to other folks I have read stuff from. Thanks for posting when you’ve got the opportunity, Guess I’ll just bookmark this blog.|

  64. Hiya, I am really glad I’ve found this information. Today bloggers publish only about gossip and web stuff and this is really annoying. A good web site with exciting content, this is what I need. Thank you for making this web site, and I will be visiting again. Do you do newsletters by email?

  65. This is very interesting, You are a very skilled blogger. I ave joined your rss feed and look forward to seeking more of your fantastic post. Also, I have shared your site in my social networks!

  66. We absolutely love your blog and find nearly all of your post’s to be what
    precisely I’m looking for. can you offer guest writers to write content to suit your needs?
    I wouldn’t mind creating a post or elaborating on some of the subjects you write about here.

    Again, awesome web site!

  67. Hiya, I am really glad I’ve found this information. Nowadays bloggers publish only about gossip and web stuff and this is really irritating. A good blog with interesting content, this is what I need. Thank you for making this web-site, and I will be visiting again. Do you do newsletters by email?

  68. Hi there. I discovered your site by means of Google at the same time as looking for a similar topic, your site got here up. It seems great. I have bookmarked it in my google bookmarks to come back then.

  69. Hey, you used to write great, but the last few posts have been kinda boring¡K I miss your great writings. Past few posts are just a little bit out of track! come on!

  70. What’s up everybody, here every one is sharing such know-how, thus
    it’s good to read this web site, and I used to visit this webpage everyday.

  71. I love your blog.. very nice colors & theme. Did you make this website yourself or did you hire someone to do itfor you? Plz reply as I’m looking to design my own blog and would like to find out where ugot this from. kudos

  72. Best video poker machines are certainly not come up with in casinos, theymay be randomly scattered to ensure that players could never get an edge for the casinos.Some in the factors will be the rules in thegame that the are playing, score with your hand, dealer’s up card and if youown an option to split or double. If undesirablehabits and wrong decisions were made, always look at what you mighthave inked different to get different results that would not hurt people around you.

  73. I’ve been surfing online more than 3 hours today, yet I never found any interesting article like yours. It is pretty worth enough for me. In my opinion, if all website owners and bloggers made good content as you did, the internet will be much more useful than ever before.

  74. you’re really a good webmaster. The web site loading velocity is incredible. It sort of feels that you’re doing any unique trick. Also, The contents are masterwork. you have done a excellent process on this matter!|

  75. Nice post. I was checking continuously this blog and I am impressed!Very helpful information specially the last part 🙂 I carefor such info much. I was looking for this certain info for a verylong time. Thank you and best of luck.

  76. I was just searching for this info for some time. After 6 hours of continuous Googleing, finally I got it in your website. I wonder what’s the lack of Google strategy that don’t rank this type of informative web sites in top of the list. Generally the top websites are full of garbage.

  77. I’d like to thank you for the efforts you’ve put in penning this site.
    I really hope to view the same high-grade content from you
    later on as well. In fact, your creative writing abilities
    has motivated me to get my own blog now 😉

  78. F*ckin’ amazing things here. I’m very satisfied to see your article. Thank you so much and i’m taking a look ahead to touch you. Will you please drop me a e-mail?

  79. I know this if off topic but I’m looking into starting my own weblog and was wondering what all is required to get setup? I’m assuming having a blog like yours would cost a pretty penny? I’m not very web savvy so I’m not 100 sure. Any tips or advice would be greatly appreciated. Thanks

  80. Great post. I used to be checking constantly this blog and I’m inspired! Extremely useful info particularly the final section 🙂 I care for such info much. I used to be seeking this certain information for a long time. Thank you and good luck.

  81. Howdy this is somewhat of off topic but I was wanting to knowif blogs use WYSIWYG editors or if you have to manually codewith HTML. I’m starting a blog soon but have nocoding skills so I wanted to get advice from someone with experience.Any help would be enormously appreciated!

  82. Awesome post. I am a normal visitor of your blog and appreciate you taking the time to maintain the excellent site. I will be a frequent visitor for a long time.

  83. Hiya, I am really glad I’ve found this information. Nowadays bloggers publish only about gossip and internet stuff and this is actually irritating. A good site with exciting content, this is what I need. Thank you for making this website, and I will be visiting again. Do you do newsletters by email?

Leave a Reply to dating site Cancel reply

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