{"id":15,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-09-21-%e5%87%b8%e5%8c%85%e7%ae%97%e6%b3%95\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-09-21-%e5%87%b8%e5%8c%85%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-09-21-%e5%87%b8%e5%8c%85%e7%ae%97%e6%b3%95\/","title":{"rendered":"2020-09-21 \u51f8\u5305\u7b97\u6cd5"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=2585&pid=7<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n

Recently, the nation was shocked by news of Sungai Kim Kim incident in Pasir Gudang, Johor, which has been polluted by chemical waste. Thousands of people who are affected had experienced nausea, dizziness and vomiting, and more than 100 schools were ordered to shut. In order to ensure that such incident will not happen again, an early warning system need o be developed so that residents can make early preparation, and authorities are able to move and act much faster.<\/p>\n

A group of scientists has formed a committee to handle the incident, and a smart system with Internet of Things (IoT) sensors was suggested. Numerous sensors which can sense and monitor damages to the environment, either air or water, have been strategically installed around the state, and their coordinates are also recorded. However, the proposed system encountered a failure during its first testing phase. They want you to fix the problem in determining whether the given coordinates of sensors are safe or in the affected areas.<\/p>\n

An affected area is defined as the polygon with the minimum length perimeter that can enclose all sensors that trigger warning signal within that area. For example, the sensors (represented by dots) of an affected area and its associated polygon, as well as safe (represented by triangles) and unsafe (represented by diamonds) points of the first dataset are illustrated below.
\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n

<\/a>\u8f93\u5165<\/h5>\n

The input will contain records of data for several test cases of affected areas. The first line of each data set contains a non-negative integer T, the number of test cases (1\u2264T\u226450). Each test case starts with two non-negative integer C and P which is the number of coordinates (3\u2264C\u226450), and points (1\u2264P\u226450), respectively. The next C lines contain coordinates (x-coordinate, y-coordinate) of each installed sensor, separated with blank spaces. The following P lines contain coordinates (x-coordinate, y-coordinate) of certain locations in the state, separated with blank spaces. All coordinates are integers between \u2212500 and 500 inclusive.<\/p>\n

<\/a>\u8f93\u51fa<\/h5>\n

For each test case, output the following item:<\/p>\n

First line: The number of the test cases. The first record corresponds to Case1, the second to Case2 , etc.<\/p>\n

Next line: A listing of all the points that appear on the perimeter of the affected area. The points must be identified in the standard form \u201cx-coordinate y- coordinate\u201d. The listing must be oriented counter-clockwise and begin and end with the same point.<\/p>\n

Last line: For each point of location in the data set, output the line:<\/p>\n

x\u2212coordinatey\u2212coordinateisstatus
where x\u2212coordinatey\u2212coordinate is the coordinate of the location from the input and status is \u2032safe\u2032 or \u2032unsafe\u2032. A location is considered unsafe it is within the sensor perimeter. A point in exactly at the edge of the perimeter is considered safe.<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
2\n6 5\n-477 -180\n31 -266\n-474 28\n147 49\n323 -53\n277 -79\n346 488\n-139 -183\n-427 129\n386 -222\n-408 -315\n5 2\n-52 -325\n104 420\n315 356\n-192 8\n493 146\n404 228\n-239 484\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
Case 1\n-477 -180\n31 -266\n323 -53\n147 49\n-474 28\n-477 -180\n346 488 is safe!\n-139 -183 is unsafe!\n-427 129 is safe!\n386 -222 is safe!\n-408 -315 is safe!\n\nCase 2\n-192 8\n-52 -325\n493 146\n315 356\n104 420\n-192 8\n404 228 is unsafe!\n-239 484 is safe!\n<\/code><\/pre>\n
\u51f8\u5305\u7b97\u6cd5<\/p>\n
#include<\/span> <\/span><\/span>\n\nusing<\/span> namespace<\/span> std;<\/span>\n\nconst<\/span> int<\/span> maxn=<\/span>1e3<\/span>+<\/span>9<\/span>;<\/span>\n\nconst<\/span> int<\/span> mod=<\/span>1e9<\/span>+<\/span>7<\/span>;<\/span>\n\nstruct<\/span> node\n{<\/span>\n    double<\/span> x,<\/span>y;<\/span>\n}<\/span>;<\/span>\n\nstruct<\/span> point\n{<\/span>\n    double<\/span> x,<\/span>y;<\/span>\n    point friend<\/span> operator<\/span> -<\/span> (<\/span>point a,<\/span>point b)<\/span>\n    {<\/span>\n        return<\/span> {<\/span>a.<\/span>x-<\/span>b.<\/span>x,<\/span>a.<\/span>y-<\/span>b.<\/span>y}<\/span>;<\/span>\n    }<\/span>\n}<\/span> p[<\/span>maxn]<\/span>,<\/span>s[<\/span>maxn]<\/span>,<\/span>query[<\/span>maxn]<\/span>;<\/span>\n\ndouble<\/span> dis<\/span>(<\/span>point a,<\/span>point b)<\/span>\n{<\/span>\n    point c=<\/span>a-<\/span>b;<\/span>\n    return<\/span> sqrt<\/span>(<\/span>c.<\/span>x*<\/span>c.<\/span>x+<\/span>c.<\/span>y*<\/span>c.<\/span>y)<\/span>;<\/span>\n}<\/span>\n\ndouble<\/span> chax<\/span>(<\/span>point a,<\/span>point b)<\/span>\/\/\u53c9\u4e58<\/span>\n{<\/span>\n    return<\/span> a.<\/span>x*<\/span>b.<\/span>y-<\/span>a.<\/span>y*<\/span>b.<\/span>x;<\/span>\n}<\/span>\n\ndouble<\/span> mulx<\/span>(<\/span>point p1,<\/span>point p2,<\/span>point p3)<\/span>\n{<\/span>\n    return<\/span> chax<\/span>(<\/span>p2-<\/span>p1,<\/span>p3-<\/span>p1)<\/span>;<\/span>\n}<\/span>\n\nbool<\/span> cmp2<\/span>(<\/span>point a,<\/span>point b)<\/span>\n{<\/span>\n    if<\/span> (<\/span>a.<\/span>x!=<\/span>b.<\/span>x)<\/span>\n        return<\/span> a.<\/span>x<<\/span>b.<\/span>x;<\/span>\n    return<\/span> a.<\/span>y<<\/span>b.<\/span>y;<\/span>\n}<\/span>\n\ndouble<\/span> xxx,<\/span>yyy;<\/span>\n\nvector<<\/span>node><\/span>v;<\/span>\n\nint<\/span> judge<\/span>(<\/span>int<\/span> i,<\/span>int<\/span> j,<\/span>int<\/span> k)<\/span>\n{<\/span>\n    double<\/span> xpa=<\/span>xxx-<\/span>v[<\/span>i]<\/span>.<\/span>x;<\/span>\n\n    double<\/span> ypa=<\/span>yyy-<\/span>v[<\/span>i]<\/span>.<\/span>y;<\/span>\n\n    double<\/span> xpb=<\/span>xxx-<\/span>v[<\/span>j]<\/span>.<\/span>x;<\/span>\n\n    double<\/span> ypb=<\/span>yyy-<\/span>v[<\/span>j]<\/span>.<\/span>y;<\/span>\n\n    double<\/span> xpc=<\/span>xxx-<\/span>v[<\/span>k]<\/span>.<\/span>x;<\/span>\n\n    double<\/span> ypc=<\/span>yyy-<\/span>v[<\/span>k]<\/span>.<\/span>y;<\/span>\n\n    double<\/span> ans1=<\/span>xpa*<\/span>ypb-<\/span>xpb*<\/span>ypa;<\/span>\n\n    double<\/span> ans2=<\/span>xpb*<\/span>ypc-<\/span>xpc*<\/span>ypb;<\/span>\n\n    double<\/span> ans3=<\/span>xpc*<\/span>ypa-<\/span>xpa*<\/span>ypc;<\/span>\n\n    if<\/span>(<\/span>ans1==<\/span>0<\/span>||<\/span>ans2==<\/span>0<\/span>||<\/span>ans3==<\/span>0<\/span>)<\/span>\n        return<\/span> 1<\/span>;<\/span>\n\n    if<\/span>(<\/span>ans1><\/span>0<\/span>&&<\/span>ans2><\/span>0<\/span>&&<\/span>ans3><\/span>0<\/span>)<\/span>\n        return<\/span> 1<\/span>;<\/span>\n\n    if<\/span>(<\/span>ans1<<\/span>0<\/span>&&<\/span>ans2<<\/span>0<\/span>&&<\/span>ans3<<\/span>0<\/span>)<\/span>\n        return<\/span> 1<\/span>;<\/span>\n\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n\n\nint<\/span> hack<\/span>(<\/span>int<\/span> i,<\/span>int<\/span> j)<\/span>\n{<\/span>\n    double<\/span> xpa=<\/span>xxx-<\/span>v[<\/span>i]<\/span>.<\/span>x;<\/span>\n\n    double<\/span> ypa=<\/span>yyy-<\/span>v[<\/span>i]<\/span>.<\/span>y;<\/span>\n\n    double<\/span> xpb=<\/span>xxx-<\/span>v[<\/span>j]<\/span>.<\/span>x;<\/span>\n\n    double<\/span> ypb=<\/span>yyy-<\/span>v[<\/span>j]<\/span>.<\/span>y;<\/span>\n\n    double<\/span> ans1=<\/span>xpa*<\/span>ypb-<\/span>xpb*<\/span>ypa;<\/span>\n\n    if<\/span>(<\/span>ans1==<\/span>0<\/span>)<\/span>\n        return<\/span> 1<\/span>;<\/span>\n\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n\n\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> T;<\/span>\n    cin>><\/span>T;<\/span>\n    int<\/span> cas=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> j=<\/span>1<\/span>;<\/span>j<=<\/span>T;<\/span>j++<\/span>)<\/span>\n    {<\/span>\n        v.<\/span>clear<\/span>(<\/span>)<\/span>;<\/span>\n        int<\/span> n,<\/span>q;<\/span>\n        cin>><\/span>n>><\/span>q;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span> i<<\/span>n;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            cin>><\/span>p[<\/span>i]<\/span>.<\/span>x>><\/span>p[<\/span>i]<\/span>.<\/span>y;<\/span>\n        }<\/span>\n\n        sort<\/span>(<\/span>p,<\/span>p+<\/span>n,<\/span>cmp2)<\/span>;<\/span>\n\n        int<\/span> m=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span> i<<\/span>n;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            while<\/span>(<\/span>m><\/span>1<\/span>&&<\/span>mulx<\/span>(<\/span>s[<\/span>m-<\/span>2<\/span>]<\/span>,<\/span>s[<\/span>m-<\/span>1<\/span>]<\/span>,<\/span>p[<\/span>i]<\/span>)<\/span><=<\/span>0<\/span>)<\/span> m--<\/span>;<\/span>\n            s[<\/span>m++<\/span>]<\/span>=<\/span>p[<\/span>i]<\/span>;<\/span>\n        }<\/span>\n\n        int<\/span> kk=<\/span>m;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>n-<\/span>2<\/span>;<\/span> i>=<\/span>0<\/span>;<\/span> i--<\/span>)<\/span>\n        {<\/span>\n            while<\/span>(<\/span>m><\/span>kk&&<\/span>mulx<\/span>(<\/span>s[<\/span>m-<\/span>2<\/span>]<\/span>,<\/span>s[<\/span>m-<\/span>1<\/span>]<\/span>,<\/span>p[<\/span>i]<\/span>)<\/span><=<\/span>0<\/span>)<\/span> m--<\/span>;<\/span>\n            s[<\/span>m++<\/span>]<\/span>=<\/span>p[<\/span>i]<\/span>;<\/span>\n        }<\/span>\n\n        if<\/span>(<\/span>n><\/span>1<\/span>)<\/span>\n            m--<\/span>;<\/span>\n\n        printf<\/span>(<\/span>\"Case %dn\"<\/span>,<\/span>j)<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span> i<<\/span>m;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            cout<<<\/span>s[<\/span>i]<\/span>.<\/span>x<<<\/span>\" \"<\/span><<<\/span>s[<\/span>i]<\/span>.<\/span>y<<<\/span>endl;<\/span>\n            v.<\/span>push_back<\/span>(<\/span>{<\/span>s[<\/span>i]<\/span>.<\/span>x,<\/span>s[<\/span>i]<\/span>.<\/span>y}<\/span>)<\/span>;<\/span>\n        }<\/span>\n\n        cout<<<\/span>s[<\/span>0<\/span>]<\/span>.<\/span>x<<<\/span>\" \"<\/span><<<\/span>s[<\/span>0<\/span>]<\/span>.<\/span>y<<<\/span>endl;<\/span>\n        for<\/span>(<\/span>int<\/span> ii=<\/span>1<\/span>;<\/span> ii<=<\/span>q;<\/span> ii++<\/span>)<\/span>\n        {<\/span>\n            scanf<\/span>(<\/span>\"%lf%lf\"<\/span>,<\/span>&<\/span>xxx,<\/span>&<\/span>yyy)<\/span>;<\/span>\n            int<\/span> flag=<\/span>1<\/span>;<\/span>\n            for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span> i<<\/span>v.<\/span>size<\/span>(<\/span>)<\/span>&&<\/span>flag;<\/span> i++<\/span>)<\/span>\n            {<\/span>\n                for<\/span>(<\/span>int<\/span> j=<\/span>i+<\/span>1<\/span>;<\/span> j<<\/span>v.<\/span>size<\/span>(<\/span>)<\/span>&&<\/span>flag;<\/span> j++<\/span>)<\/span>\n                {<\/span>\n                    for<\/span>(<\/span>int<\/span> k=<\/span>j+<\/span>1<\/span>;<\/span> k<<\/span>v.<\/span>size<\/span>(<\/span>)<\/span>&&<\/span>flag;<\/span> k++<\/span>)<\/span>\n                    {<\/span>\n                        if<\/span>(<\/span>judge<\/span>(<\/span>i,<\/span>j,<\/span>k)<\/span>)<\/span>\n                        {<\/span>\n                            flag=<\/span>0<\/span>;<\/span>\n                        }<\/span>\n                    }<\/span>\n                }<\/span>\n            }<\/span>\n\n            for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span> i<<\/span>v.<\/span>size<\/span>(<\/span>)<\/span>-<\/span>1<\/span>&&<\/span>!<\/span>flag;<\/span> i++<\/span>)<\/span>\n                if<\/span>(<\/span>hack<\/span>(<\/span>i,<\/span>i+<\/span>1<\/span>)<\/span>)<\/span>\n                    flag=<\/span>1<\/span>;<\/span>\n            if<\/span>(<\/span>hack<\/span>(<\/span>v.<\/span>size<\/span>(<\/span>)<\/span>-<\/span>1<\/span>,<\/span>0<\/span>)<\/span>)<\/span>\n                flag=<\/span>1<\/span>;<\/span>\n\n            if<\/span>(<\/span>!<\/span>flag)<\/span>\n            {<\/span>\n                printf<\/span>(<\/span>\"%.0f %.0f is unsafe!n\"<\/span>,<\/span>xxx,<\/span>yyy)<\/span>;<\/span>\n            }<\/span>\n            else<\/span>\n            {<\/span>\n                printf<\/span>(<\/span>\"%.0f %.0f is safe!n\"<\/span>,<\/span>xxx,<\/span>yyy)<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        printf<\/span>(<\/span>\"n\"<\/span>)<\/span>;<\/span>\n    }<\/span>\n}<\/span>\n<\/code><\/pre>\n
\u51f8\u5305\u7b97\u6cd5\u6a21\u677f<\/p>\n
\/\/AndrewScan<\/span>\n\/* \n * @Author: lzyws739307453 \n * @Language: C++ \n *\/<\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\nconst<\/span> int<\/span> MAXN =<\/span> 105<\/span>;<\/span>\nconst<\/span> double<\/span> eps =<\/span> 1e-8<\/span>;<\/span>\ntypedef<\/span> struct<\/span> Point {<\/span>\n    double<\/span> x,<\/span> y;<\/span>\n    Point<\/span>(<\/span>double<\/span> x_ =<\/span> 0<\/span>,<\/span> double<\/span> y_ =<\/span> 0<\/span>)<\/span> :<\/span> x<\/span>(<\/span>x_)<\/span>,<\/span> y<\/span>(<\/span>y_)<\/span> {<\/span>}<\/span>\n    bool<\/span> operator<\/span> <<\/span> (<\/span>const<\/span> Point&<\/span> s)<\/span> const<\/span> {<\/span>\n        return<\/span> x !=<\/span> s.<\/span>x ?<\/span> x <<\/span> s.<\/span>x :<\/span> y <<\/span> s.<\/span>y;<\/span>\n    }<\/span>\n}<\/span>vect;<\/span>\nstruct<\/span> Point p[<\/span>MAXN]<\/span>,<\/span> S[<\/span>MAXN]<\/span>,<\/span> s;<\/span>\nint<\/span> sgn<\/span>(<\/span>double<\/span> x)<\/span> {<\/span>\n    return<\/span> x <<\/span> -<\/span>eps ?<\/span> -<\/span>1<\/span> :<\/span> x ><\/span> eps ?<\/span> 1<\/span> :<\/span> 0<\/span>;<\/span>\n}<\/span>\nvect operator<\/span> -<\/span> (<\/span>const<\/span> Point a,<\/span> const<\/span> Point b)<\/span> {<\/span>\n    return<\/span> vect<\/span>(<\/span>a.<\/span>x -<\/span> b.<\/span>x,<\/span> a.<\/span>y -<\/span> b.<\/span>y)<\/span>;<\/span>\n}<\/span>\ndouble<\/span> Cross<\/span>(<\/span>const<\/span> vect a,<\/span> const<\/span> vect b)<\/span> {<\/span>\n    return<\/span> a.<\/span>x *<\/span> b.<\/span>y -<\/span> a.<\/span>y *<\/span> b.<\/span>x;<\/span>\n}<\/span>\ndouble<\/span> dist<\/span>(<\/span>const<\/span> Point a,<\/span> const<\/span> Point b)<\/span> {<\/span>\n    return<\/span> sqrt<\/span>(<\/span>(<\/span>a.<\/span>x -<\/span> b.<\/span>x)<\/span> *<\/span> (<\/span>a.<\/span>x -<\/span> b.<\/span>x)<\/span> +<\/span> (<\/span>a.<\/span>y -<\/span> b.<\/span>y)<\/span> *<\/span> (<\/span>a.<\/span>y -<\/span> b.<\/span>y)<\/span>)<\/span>;<\/span>\n}<\/span>\nbool<\/span> Onleft<\/span>(<\/span>const<\/span> Point a,<\/span> const<\/span> Point b,<\/span> const<\/span> Point c)<\/span> {<\/span>\n    return<\/span> sgn<\/span>(<\/span>Cross<\/span>(<\/span>b -<\/span> a,<\/span> c -<\/span> a)<\/span>)<\/span> ><\/span> 0<\/span>;<\/span>\n}<\/span>\nbool<\/span> InTB<\/span>(<\/span>const<\/span> Point p[<\/span>]<\/span>,<\/span> const<\/span> Point s,<\/span> int<\/span> n)<\/span> {<\/span>\n    for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>\n        int<\/span> j =<\/span> (<\/span>i +<\/span> 1<\/span>)<\/span> %<\/span> n;<\/span>\n        if<\/span> (<\/span>Cross<\/span>(<\/span>p[<\/span>j]<\/span> -<\/span> p[<\/span>i]<\/span>,<\/span> s -<\/span> p[<\/span>i]<\/span>)<\/span> <=<\/span> 0<\/span>)<\/span>\n            return<\/span> false<\/span>;<\/span>\n    }<\/span>\n    return<\/span> true<\/span>;<\/span>\n}<\/span>\nint<\/span> AndrewScan<\/span>(<\/span>Point p[<\/span>]<\/span>,<\/span> int<\/span> n)<\/span> {<\/span>\n    sort<\/span>(<\/span>p,<\/span> p +<\/span> n)<\/span>;<\/span>\n    int<\/span> top =<\/span> 0<\/span>;<\/span>\n    for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>\n        while<\/span> (<\/span>top ><\/span> 1<\/span> &&<\/span> !<\/span>Onleft<\/span>(<\/span>S[<\/span>top -<\/span> 2<\/span>]<\/span>,<\/span> S[<\/span>top -<\/span> 1<\/span>]<\/span>,<\/span> p[<\/span>i]<\/span>)<\/span>)<\/span>\n            top--<\/span>;<\/span>\n        S[<\/span>top++<\/span>]<\/span> =<\/span> p[<\/span>i]<\/span>;<\/span>\n    }<\/span>\n    int<\/span> tmp =<\/span> top;<\/span>\n    for<\/span> (<\/span>int<\/span> i =<\/span> n -<\/span> 2<\/span>;<\/span> i >=<\/span> 0<\/span>;<\/span> i--<\/span>)<\/span> {<\/span>\n        while<\/span> (<\/span>top ><\/span> tmp &&<\/span> !<\/span>Onleft<\/span>(<\/span>S[<\/span>top -<\/span> 2<\/span>]<\/span>,<\/span> S[<\/span>top -<\/span> 1<\/span>]<\/span>,<\/span> p[<\/span>i]<\/span>)<\/span>)<\/span>\n            top--<\/span>;<\/span>\n        S[<\/span>top++<\/span>]<\/span> =<\/span> p[<\/span>i]<\/span>;<\/span>\n    }<\/span>\n    return<\/span> top;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span> {<\/span>\n    int<\/span> n,<\/span> q,<\/span> t,<\/span> cnt,<\/span> kase =<\/span> 0<\/span>;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span> &<\/span>t)<\/span>;<\/span>\n    while<\/span> (<\/span>t--<\/span>)<\/span> {<\/span>\n        scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span> &<\/span>n,<\/span> &<\/span>q)<\/span>;<\/span>\n        for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span>\n            scanf<\/span>(<\/span>\"%lf%lf\"<\/span>,<\/span> &<\/span>p[<\/span>i]<\/span>.<\/span>x,<\/span> &<\/span>p[<\/span>i]<\/span>.<\/span>y)<\/span>;<\/span>\n        cnt =<\/span> AndrewScan<\/span>(<\/span>p,<\/span> n)<\/span>;<\/span>\n        if<\/span> (<\/span>n ><\/span> 1<\/span>)<\/span>\n            cnt--<\/span>;<\/span>\n        if<\/span> (<\/span>kase)<\/span>\n            printf<\/span>(<\/span>\"n\"<\/span>)<\/span>;<\/span>\n        printf<\/span>(<\/span>\"Case %dn\"<\/span>,<\/span> ++<\/span>kase)<\/span>;<\/span>\n        for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> cnt;<\/span> i++<\/span>)<\/span>\n            printf<\/span>(<\/span>\"%.0lf %.0lfn\"<\/span>,<\/span> S[<\/span>i]<\/span>.<\/span>x,<\/span> S[<\/span>i]<\/span>.<\/span>y)<\/span>;<\/span>\n        printf<\/span>(<\/span>\"%.0lf %.0lfn\"<\/span>,<\/span> S[<\/span>0<\/span>]<\/span>.<\/span>x,<\/span> S[<\/span>0<\/span>]<\/span>.<\/span>y)<\/span>;<\/span>\n        while<\/span> (<\/span>q--<\/span>)<\/span> {<\/span>\n            scanf<\/span>(<\/span>\"%lf%lf\"<\/span>,<\/span> &<\/span>s.<\/span>x,<\/span> &<\/span>s.<\/span>y)<\/span>;<\/span>\n            printf<\/span>(<\/span>\"%.0lf %.0lf \"<\/span>,<\/span> s.<\/span>x,<\/span> s.<\/span>y)<\/span>;<\/span>\n            if<\/span> (<\/span>InTB<\/span>(<\/span>S,<\/span> s,<\/span> cnt)<\/span>)<\/span>\n                printf<\/span>(<\/span>\"is unsafe!n\"<\/span>)<\/span>;<\/span>\n            else<\/span> printf<\/span>(<\/span>\"is safe!n\"<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n\n<\/code><\/pre>\n
#include<\/span><\/span><\/span>\n#include<\/span><\/span><\/span>\n#include<\/span><\/span><\/span>\n#include<\/span><\/span><\/span>\n#include<\/span><\/span><\/span>\n#define<\/span> PI 3.1415926535<\/span>\nusing<\/span> namespace<\/span> std;<\/span>\nstruct<\/span> node\n{<\/span>\n    int<\/span> x,<\/span>y;<\/span>\n}<\/span>;<\/span>\nnode vex[<\/span>1000<\/span>]<\/span>;<\/span>\/\/\u5b58\u5165\u7684\u6240\u6709\u7684\u70b9<\/span>\nnode stackk[<\/span>1000<\/span>]<\/span>;<\/span>\/\/\u51f8\u5305\u4e2d\u6240\u6709\u7684\u70b9<\/span>\nint<\/span> xx,<\/span>yy;<\/span>\nbool<\/span> cmp1<\/span>(<\/span>node a,<\/span>node b)<\/span>\/\/\u6392\u5e8f\u627e\u7b2c\u4e00\u4e2a\u70b9<\/span>\n{<\/span>\n    if<\/span>(<\/span>a.<\/span>y==<\/span>b.<\/span>y)<\/span>\n        return<\/span> a.<\/span>x<<\/span>b.<\/span>x;<\/span>\n    else<\/span>\n        return<\/span> a.<\/span>y<<\/span>b.<\/span>y;<\/span>\n}<\/span>\nint<\/span> cross<\/span>(<\/span>node a,<\/span>node b,<\/span>node c)<\/span>\/\/\u8ba1\u7b97\u53c9\u79ef<\/span>\n{<\/span>\n    return<\/span> (<\/span>b.<\/span>x-<\/span>a.<\/span>x)<\/span>*<\/span>(<\/span>c.<\/span>y-<\/span>a.<\/span>y)<\/span>-<\/span>(<\/span>c.<\/span>x-<\/span>a.<\/span>x)<\/span>*<\/span>(<\/span>b.<\/span>y-<\/span>a.<\/span>y)<\/span>;<\/span>\n}<\/span>\ndouble<\/span> dis<\/span>(<\/span>node a,<\/span>node b)<\/span>\/\/\u8ba1\u7b97\u8ddd\u79bb<\/span>\n{<\/span>\n    return<\/span> sqrt<\/span>(<\/span>(<\/span>a.<\/span>x-<\/span>b.<\/span>x)<\/span>*<\/span>(<\/span>a.<\/span>x-<\/span>b.<\/span>x)<\/span>*<\/span>1.0<\/span>+<\/span>(<\/span>a.<\/span>y-<\/span>b.<\/span>y)<\/span>*<\/span>(<\/span>a.<\/span>y-<\/span>b.<\/span>y)<\/span>)<\/span>;<\/span>\n}<\/span>\nbool<\/span> cmp2<\/span>(<\/span>node a,<\/span>node b)<\/span>\/\/\u6781\u89d2\u6392\u5e8f\u53e6\u4e00\u79cd\u65b9\u6cd5\uff0c\u901f\u5ea6\u5feb<\/span>\n{<\/span>\n    if<\/span>(<\/span>atan2<\/span>(<\/span>a.<\/span>y-<\/span>yy,<\/span>a.<\/span>x-<\/span>xx)<\/span>!=<\/span>atan2<\/span>(<\/span>b.<\/span>y-<\/span>yy,<\/span>b.<\/span>x-<\/span>xx)<\/span>)<\/span>\n        return<\/span> (<\/span>atan2<\/span>(<\/span>a.<\/span>y-<\/span>yy,<\/span>a.<\/span>x-<\/span>xx)<\/span>)<\/span><<\/span>(<\/span>atan2<\/span>(<\/span>b.<\/span>y-<\/span>yy,<\/span>b.<\/span>x-<\/span>xx)<\/span>)<\/span>;<\/span>\n    return<\/span> a.<\/span>x<<\/span>b.<\/span>x;<\/span>\n}<\/span>\nbool<\/span> cmp<\/span>(<\/span>node a,<\/span>node b)<\/span>\/\/\u6781\u89d2\u6392\u5e8f<\/span>\n{<\/span>\n    int<\/span> m=<\/span>cross<\/span>(<\/span>vex[<\/span>0<\/span>]<\/span>,<\/span>a,<\/span>b)<\/span>;<\/span>\n    if<\/span>(<\/span>m><\/span>0<\/span>)<\/span>\n        return<\/span> 1<\/span>;<\/span>\n    else<\/span> if<\/span>(<\/span>m==<\/span>0<\/span>&&<\/span>dis<\/span>(<\/span>vex[<\/span>0<\/span>]<\/span>,<\/span>a)<\/span>-<\/span>dis<\/span>(<\/span>vex[<\/span>0<\/span>]<\/span>,<\/span>b)<\/span><=<\/span>0<\/span>)<\/span>\n        return<\/span> 1<\/span>;<\/span>\n    else<\/span> return<\/span> 0<\/span>;<\/span>\n    \/*if(m==0)\n        return dis(vex[0],a)-dis(vex[0],b)<=0?true:false;\n    else\n        return m>0?true:false;*\/<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> t,<\/span>L;<\/span>\n    while<\/span>(<\/span>~<\/span>scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>t)<\/span>,<\/span>t)<\/span>\n    {<\/span>\n        int<\/span> i;<\/span>\n        for<\/span>(<\/span>i=<\/span>0<\/span>;<\/span> i<<\/span>t;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>vex[<\/span>i]<\/span>.<\/span>x,<\/span>&<\/span>vex[<\/span>i]<\/span>.<\/span>y)<\/span>;<\/span>\n        }<\/span>\n        if<\/span>(<\/span>t==<\/span>1<\/span>)<\/span>\n            printf<\/span>(<\/span>\"%.2fn\"<\/span>,<\/span>0.00<\/span>)<\/span>;<\/span>\n        else<\/span> if<\/span>(<\/span>t==<\/span>2<\/span>)<\/span>\n            printf<\/span>(<\/span>\"%.2fn\"<\/span>,<\/span>dis<\/span>(<\/span>vex[<\/span>0<\/span>]<\/span>,<\/span>vex[<\/span>1<\/span>]<\/span>)<\/span>)<\/span>;<\/span>\n        else<\/span>\n        {<\/span>\n            memset<\/span>(<\/span>stackk,<\/span>0<\/span>,<\/span>sizeof<\/span>(<\/span>stackk)<\/span>)<\/span>;<\/span>\n            sort<\/span>(<\/span>vex,<\/span>vex+<\/span>t,<\/span>cmp1)<\/span>;<\/span>\n            stackk[<\/span>0<\/span>]<\/span>=<\/span>vex[<\/span>0<\/span>]<\/span>;<\/span>\n            xx=<\/span>stackk[<\/span>0<\/span>]<\/span>.<\/span>x;<\/span>\n            yy=<\/span>stackk[<\/span>0<\/span>]<\/span>.<\/span>y;<\/span>\n            sort<\/span>(<\/span>vex+<\/span>1<\/span>,<\/span>vex+<\/span>t,<\/span>cmp2)<\/span>;<\/span>\/\/cmp2\u662f\u66f4\u5feb\u7684\uff0ccmp\u66f4\u5bb9\u6613\u7406\u89e3<\/span>\n            stackk[<\/span>1<\/span>]<\/span>=<\/span>vex[<\/span>1<\/span>]<\/span>;<\/span>\/\/\u5c06\u51f8\u5305\u4e2d\u7684\u7b2c\u4e24\u4e2a\u70b9\u5b58\u5165\u51f8\u5305\u7684\u7ed3\u6784\u4f53\u4e2d<\/span>\n            int<\/span> top=<\/span>1<\/span>;<\/span>\/\/\u6700\u540e\u51f8\u5305\u4e2d\u62e5\u6709\u70b9\u7684\u4e2a\u6570<\/span>\n            for<\/span>(<\/span>i=<\/span>2<\/span>;<\/span> i<<\/span>t;<\/span> i++<\/span>)<\/span>\n            {<\/span>\n                while<\/span>(<\/span>i>=<\/span>1<\/span>&&<\/span>cross<\/span>(<\/span>stackk[<\/span>top-<\/span>1<\/span>]<\/span>,<\/span>stackk[<\/span>top]<\/span>,<\/span>vex[<\/span>i]<\/span>)<\/span><<\/span>0<\/span>)<\/span>   \/\/\u5bf9\u4f7f\u7528\u6781\u89d2\u6392\u5e8f\u7684i>=1\u6709\u65f6\u53ef\u4ee5\u4e0d\u7528\uff0c\u4f46\u52a0\u4e0a\u603b\u662f\u597d\u7684<\/span>\n                    top--<\/span>;<\/span>\n                stackk[<\/span>++<\/span>top]<\/span>=<\/span>vex[<\/span>i]<\/span>;<\/span>                                    \/\/\u63a7\u5236<0\u6216<=0\u53ef\u4ee5\u63a7\u5236\u91cd\u70b9\uff0c\u5171\u7ebf\u7684\uff0c\u5177\u4f53\u89c6\u9898\u76ee\u800c\u5b9a\u3002<\/span>\n            }<\/span>\n            double<\/span> s=<\/span>0<\/span>;<\/span>\n            \/\/for(i=1; i<=top; i++)\/\/\u8f93\u51fa\u51f8\u5305\u4e0a\u7684\u70b9<\/span>\n            \/\/cout<\n            for<\/span>(<\/span>i=<\/span>1<\/span>;<\/span> i<=<\/span>top;<\/span> i++<\/span>)<\/span>   \/\/\u8ba1\u7b97\u51f8\u5305\u7684\u5468\u957f<\/span>\n                s+<\/span>=<\/span>dis<\/span>(<\/span>stackk[<\/span>i-<\/span>1<\/span>]<\/span>,<\/span>stackk[<\/span>i]<\/span>)<\/span>;<\/span>\n            s+<\/span>=<\/span>dis<\/span>(<\/span>stackk[<\/span>top]<\/span>,<\/span>vex[<\/span>0<\/span>]<\/span>)<\/span>;<\/span>\/\/\u6700\u540e\u4e00\u4e2a\u70b9\u548c\u7b2c\u4e00\u4e2a\u70b9\u4e4b\u95f4\u7684\u8ddd\u79bb<\/span>\n            \/*s+=2*PI*L;\n            int ans=s+0.5;\/\/\u56db\u820d\u4e94\u5165\n            printf(\"%dn\",ans);*\/<\/span>\n            printf<\/span>(<\/span>\"%.2lfn\"<\/span>,<\/span>s)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-15","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/15","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=15"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/15\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=15"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=15"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=15"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}