【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;
}

162 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. It’s amazing to pay a visit this website and reading the views of all mates concerning this
    article, while I am also eager of getting familiarity.

  9. 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

  10. 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!

  11. 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.

  12. 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

  13. 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!

  14. 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.

  15. 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.

  16. 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!

  17. 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!

  18. 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.

  19. 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!

  20. 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

  21. 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!

  22. 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!

  23. 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!

  24. 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.

  25. 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.

  26. 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.

  27. 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.

  28. 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!

  29. 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!|

  30. 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.

  31. 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.

  32. 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.

  33. 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!

  34. 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.

  35. 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.

  36. 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.

  37. 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.

  38. 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!

  39. 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

  40. 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?

  41. 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!

  42. 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.

  43. 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!

  44. 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.

  45. 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.

  46. 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.

  47. 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!

  48. 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.

  49. 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.

  50. 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.

  51. 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.

  52. 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!

  53. 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!

  54. 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.

  55. 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.

  56. 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.

发表评论

电子邮件地址不会被公开。 必填项已用*标注