SRM562 Div1 Medium(500) CheckerFreeness

TopCoder

CheckerFreeness

わかんね(・3・)

#include <vector>
#include <string>
#include <complex>
#include <numeric>
#include <sstream>
#include <algorithm>
using namespace std;

typedef complex<long long> comp;

inline int sign(long long a) { return a>0LL?1:a<0LL?-1:0; }

//  外積
inline long long cross( const comp &a, const comp &b ) { return a.real()*b.imag()-a.imag()*b.real(); }

//  線分の交差判定
inline bool intersect( const comp &a1, const comp &a2, const comp &b1, const comp &b2 )
{
    return sign(cross(a2-a1,b1-a1)) * sign(cross(a2-a1,b2-a1)) <= 0 &&
           sign(cross(b2-b1,a1-b1)) * sign(cross(b2-b1,a2-b1)) <= 0;
}

//  凸包
bool convexfull_cmp( comp a, comp b )
{
    if(a.real()!=b.real())return a.real()<b.real();
    return a.imag()<b.imag();
}
vector<comp> convexfull( vector<comp> p )
{
    int n=(int)p.size();
    sort(p.begin(),p.end(),convexfull_cmp);
    vector<comp>r(2*n);
    int k=0;
    for(int i=0;i<n;i++){
        while(k>1&&cross(r[k-1]-r[k-2],p[i]-r[k-1])<=0)k--;r[k++]=p[i];}
    for(int i=n-2,t=k;i>=0;i--){
        while(k>t&&cross(r[k-1]-r[k-2],p[i]-r[k-1])<=0)k--;r[k++]=p[i];}
    r.resize(k-1);
    return r;
}

class CheckerFreeness{public:
string isFree( vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY )
{
    vector<comp> W, B;

    stringstream sswx(accumulate(whiteX.begin(),whiteX.end(),string()));
    stringstream sswy(accumulate(whiteY.begin(),whiteY.end(),string()));
    long long x, y;
    while ( (sswx>>x)&&(sswy>>y) )
        W.push_back(comp(x,y));
    stringstream ssbx(accumulate(blackX.begin(),blackX.end(),string()));
    stringstream ssby(accumulate(blackY.begin(),blackY.end(),string()));
    while ( (ssbx>>x)&&(ssby>>y) )
        B.push_back(comp(x,y));

    vector<comp> CW = convexfull(W);
    vector<comp> CB = convexfull(B);
    CW.push_back(CW[0]);
    CB.push_back(CB[0]);

    for ( int w1=0; w1<(int)W.size(); w1++ )
    for ( int w2=w1+1; w2<(int)W.size(); w2++ )
        for ( int b=0; b<(int)CB.size()-1; b++ )
            if ( intersect(W[w1],W[w2],CB[b],CB[b+1]) )
                return "NO";

    for ( int b1=0; b1<(int)B.size(); b1++ )
    for ( int b2=b1+1; b2<(int)B.size(); b2++ )
        for ( int w=0; w<(int)CW.size()-1; w++ )
            if ( intersect(B[b1],B[b2],CW[w],CW[w+1]) )
                return "NO";

    return "YES";
}};