[TIOJ] 1257 皮皮歷險記Online

LINK：https://tioj.infor.org/problems/1257
　　題目就告訴我們要作凸包了=_="，然後我做完之後弄一弄丟上去就不斷地WA!?
　　最後丟了一些case來return -1發現了奇妙的事實(?)，消失的皮皮不管怎樣都是不再凸包上的，以我的理解這樣好像是不符合題意的，不過AC了@@

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> Point;
typedef vector<int> VI;
#define endl '\n'
#define x first
#define y second
#define debug(args...){string _s = #args; replace(all(_s),',',' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); error(_it,args);}

bool is_debug = 0;
void error(istream_iterator<string> _it)
{
    if(is_debug) cerr << endl;
}
template<typename T,typename... Args>
void error(istream_iterator<string> it,T a, Args... args)
{
    if(is_debug)
    {
        cerr << *it << " = " << a << "   ";
        error(++it,args...);
    }
}
inline double cross(Point o,Point a,Point b)
{
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}

int n,k;
Point pipi[2][500009],P[1000009],CH[1000009];
map<int,string> hello;
main()
{
    while(cin >> n >> k && n && k)
    {
        memset(pipi,0,sizeof(pipi)); memset(P,0,sizeof(P)); memset(CH,0,sizeof(CH));
        hello.clear();
        for(int i = 0; i < k; i++)
        {
            string a; cin >> a;
            hello[i] = a;
            int aa,aaa,aaaa,aaaaa;
            cin >> aa >> aaa >> aaaa >> aaaaa;
            pipi[0][i] = {aa,aaa};
            pipi[1][i] = {aaaa,aaaaa};
            P[2*i] = pipi[0][i];
            P[2*i+1] = pipi[1][i];
        }
        sort(P,P+2*k);
        int m = 0;
        for(int i = 0; i < 2*k; i++)
        {
            while(m >= 2 && cross(CH[m-2],CH[m-1],P[i]) <= 0) m--;
            CH[m++] = P[i];
        }
        for(int i = 2*k-2, t = m+1; i >= 0; i--)
        {
            while(m >= t && cross(CH[m-2],CH[m-1],P[i]) <= 0) m--;
            CH[m++] = P[i];
        }
        m--;
        sort(CH,CH+m);
        for(int i = 0; i < k; i++)
        {
            cout << hello[i] << ":";
            int cnt = 0;
            for(int j = 0; j < 2; j++)
                cnt += (binary_search(CH,CH+m,pipi[j][i]));
            cout << cnt << endl;
        }
    }
}