Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2402-eb935242
この記事にトラックバックする(FC2ブログユーザー)

SRM562 DIV1 MEDIUM - CheckerFreeness (この記事を編集する[管理者用])

Source

TopCoder SRM562 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

2次元平面上に白い点が222個以下と黒い点が222個以下与えられる.
順番に白い点,黒い点,白い点,黒い点を結んで凸な四角形が作れるかどうかを判定する問題.
どの3点も同一直線上になく,2点の場所は一致しない.

解法

凸な四角形は対角線が交わるので,白い点を2個,黒い点を2個選んで,白い点から成る線分,黒い点から成る線分が交わることがあるかどうかを判定する問題になる.
白い点から成る凸包,黒い点から成る凸包を求める.
交わるなら,白い点か,黒い点か,どちらかは凸包の辺になることがわかる.
なぜなら,まず,凸包の辺が交わっている,凸包が共通部分を持たないなら自明.
残りは,片方の凸包が,もう片方の凸包の中にある場合だけ.この場合,交わるなら中の凸包の辺と必ず交わる.
仮に中にある凸包を白,外側にある凸包を黒とする.
白い凸包の中に黒い点があれば,その点から外側の点に線を引くと,白い凸包の辺と交わる.
そうでないなら,黒い2点は白い凸包の外であり,白い線分(白い凸包の中の線)と交わるなら,白い凸包の辺とも交わるのは絵を思い浮かべればわかると思う.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define EPS 1e-10
#define PI 3.141592653589793238462
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
typedef struct struct_point{double x,y;}pnt;

int doubleSign(double a){if(a>EPS) return 1; if(a<-EPS) return -1; return 0;}
int doubleSignR(double a,double b){ if(doubleSign(b)!=0 && doubleSign(a/b-1)==0) return 0; return doubleSign(a-b);}
int pntSign(pnt a){int i=doubleSign(a.x); if(i) return i; return doubleSign(a.y);}

pnt pntPlus(pnt a,pnt b){a.x+=b.x; a.y+=b.y; return a;}
pnt pntMinus(pnt a,pnt b){a.x-=b.x; a.y-=b.y; return a;}
pnt pntMultiple(pnt a,pnt b){pnt c; c.x=a.x*b.x-a.y*b.y; c.y=a.x*b.y+a.y*b.x; return c;}
pnt pntMultipleDouble(pnt a,double k){a.x*=k; a.y*=k; return a;}

int pntIsEqual(pnt a,pnt b){return pntSign(pntMinus(a,b))==0;}

double pntLength(pnt a){return sqrt(a.x*a.x+a.y*a.y);}
double pntLength2(pnt a){return a.x*a.x+a.y*a.y;}
double pntDistance(pnt a,pnt b){return pntLength(pntMinus(a,b));}
double pntDistance2(pnt a,pnt b){return pntLength2(pntMinus(a,b));}
double pntArgument(pnt a){return atan2(a.y,a.x);}

pnt pntNormalize(pnt a){double n=pntLength(a); a.x/=n; a.y/=n; return a;}
double pntInnerProduct(pnt a,pnt b){return a.x*b.x+a.y*b.y;}
double pntOuterProduct(pnt a,pnt b){return a.x*b.y-a.y*b.x;}

pnt pntGenerator(double x,double y){pnt res; res.x=x; res.y=y; return res;}

pnt pntPolar(double r,double t){pnt a; a.x=r*cos(t); a.y=r*sin(t); return a;}
void pntSort(pnt d[],int s){int i,j;pnt k,t;if(s<=1)return;k=pntMultipleDouble(pntPlus(d[0],d[s-1]),1/2.0);i=-1;j=s;for(;;){while(pntSign(pntMinus(d[++i],k))==-1);while(pntSign(pntMinus(d[--j],k))==1);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}pntSort(d,i);pntSort(d+j+1,s-j-1);}

int read_int_from_char(const char in[],int l,int ret[]){
  int i,n,fg,mfg;
  if(l<0) {for(i=0;;i++) if(in[i]<' ') break; l=i;}
  n=0; fg=0; mfg=0; ret[0]=0;
  rep(i,l+1){
    if(in[i]=='-'){mfg=1; continue;}
    if(isdigit(in[i])){ret[n]=ret[n]*10+in[i]-'0'; fg=1; continue;}
    if(!fg) continue;
    fg=0; if(mfg){ret[n]=-ret[n]; mfg=0;}
    ret[++n]=0;
  }
  return n;
}

int pntCCW(pnt a,pnt b,pnt c){
  double tmp;
  b=pntMinus(b,a); c=pntMinus(c,a);
  tmp = pntOuterProduct(b,c);
  if( doubleSign(tmp) ) return doubleSign( tmp );
  if( doubleSign( pntInnerProduct(b,c) ) == -1 ) return 2;
  if( doubleSign( pntLength(c)-pntLength(b) ) == 1 ) return -2;
  return 0;
}

int pntConvexHull(pnt p[],int size,pnt res[]){
  int i,res_size=0,t;
  for(i=0;i<size;res[res_size++]=p[i++])    while(res_size>=2 && pntCCW(res[res_size-2],res[res_size-1],p[i])<=0) res_size--;
  t=res_size;
  for(i=size-2;i>=0;res[res_size++]=p[i--]) while(res_size> t && pntCCW(res[res_size-2],res[res_size-1],p[i])<=0) res_size--;
  return res_size-1;
}

#define ll long long

ll cro(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){
  x2 -= x1;
  y2 -= y1;
  x3 -= x1;
  y3 -= y1;
  return x2*y3 - x3*y2;
}

int is_cro(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4){
  ll a, b;
  a = cro(x1, y1, x2, y2, x3, y3);
  b = cro(x1, y1, x2, y2, x4, y4);
  if(a > 0 && b > 0) return 0;
  if(a < 0 && b < 0) return 0;
  a = cro(x3, y3, x4, y4, x1, y1);
  b = cro(x3, y3, x4, y4, x2, y2);
  if(a > 0 && b > 0) return 0;
  if(a < 0 && b < 0) return 0;
  return 1;
}

class CheckerFreeness {
public:
string isFree(vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY) {
  int i, j, k;

  string wXstr, wYstr, bXstr, bYstr;
  int ws, bs, wx[333], wy[333], bx[333], by[333];
  pnt wp[333], bp[333], tmpp[333]; int wps, bps;

  int x1, x2, y1, y2;

  rep(i,whiteX.size()) wXstr += whiteX[i];
  rep(i,whiteY.size()) wYstr += whiteY[i];
  rep(i,blackX.size()) bXstr += blackX[i];
  rep(i,blackY.size()) bYstr += blackY[i];

  ws = read_int_from_char(wXstr.c_str(), -1, wx);
  ws = read_int_from_char(wYstr.c_str(), -1, wy);
  bs = read_int_from_char(bXstr.c_str(), -1, bx);
  bs = read_int_from_char(bYstr.c_str(), -1, by);

  rep(i,ws) wp[i] = pntGenerator(wx[i], wy[i]);
  rep(i,bs) bp[i] = pntGenerator(bx[i], by[i]);
  pntSort(wp, ws);
  pntSort(bp, bs);

  wps = ws; bps = bs;
  if(ws >= 3){
    wps = pntConvexHull(wp, wps, tmpp);
    rep(i,wps) wp[i] = tmpp[i];
  }
  if(bs >= 3){
    bps = pntConvexHull(bp, bps, tmpp);
    rep(i,bps) bp[i] = tmpp[i];
  }

  rep(k,bps){
    x1 = (int)(bp[k].x        +0.5);  y1 = (int)(bp[k].y        +0.5);
    x2 = (int)(bp[(k+1)%bps].x+0.5);  y2 = (int)(bp[(k+1)%bps].y+0.5);
    rep(i,ws) REP(j,i+1,ws) if(is_cro(x1,y1,x2,y2,wx[i],wy[i],wx[j],wy[j])) return "NO";
  }

  rep(k,wps){
    x1 = (int)(wp[k].x        +0.5);  y1 = (int)(wp[k].y        +0.5);
    x2 = (int)(wp[(k+1)%wps].x+0.5);  y2 = (int)(wp[(k+1)%wps].y+0.5);
    rep(i,bs) REP(j,i+1,bs) if(is_cro(x1,y1,x2,y2,bx[i],by[i],bx[j],by[j])) return "NO";
  }

  return "YES";
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2402-eb935242
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。