yukicoder No.55 - 正方形を描くだけの簡単なお仕事です。

Source

ニコニコミュニティ
問題文

問題概要

$2$ 次元平面上の相異なる $3$ つの格子点 $(X_1,Y_1), (X_2,Y_2), (X_3,Y_3)$ が与えられるので,この $3$ 点を頂点として含むような正方形を作った時,残りの頂点の座標を求める問題.
答えが存在しないならそれを指摘する.
正方形の各辺は,軸に平行である必要はない.

解法

正方形の点を反時計回りに $P_1,P_2,P_3,P_4$ とすると,ベクトル $P_k - P_{k-1}$ はベクトル $P_{k-1} - P_{k-2}$ を $90$ 度回転しているものになっているはずである.
答えが存在するなら,与えられた $3$ 点をうまく入れ替えると,それぞれ $P_1,P_2,P_3$ にできるから,入れ替え方を全部試して,上の関係が成り立っているか,上の関係から $P_4$ の座標を求めれば良い.
座標の値が小さいので,答えの候補を全探索して,実際に,正方形になっているかどうかを判定しても良い.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}

int main(){
  int i, j, k;
  void *mem=malloc(10000000);

  int x[3], y[3];
  int X[4], Y[4];
  int d[3] = {0,1,2};
  int dx, dy, nx, ny;
  int ok = 0;

  rep(i,3) reader(x+i,y+i);

  do{
    rep(i,3) X[i] = x[d[i]], Y[i] = y[d[i]];
    
    dx = X[1] - X[0];
    dy = Y[1] - Y[0];

    nx = X[1] - dy;
    ny = Y[1] + dx;
    if(nx != X[2] || ny != Y[2]) continue;
    
    nx = X[2] - dx;
    ny = Y[2] - dy;
    X[3] = nx;
    Y[3] = ny;
    
    nx = X[3] + dy;
    ny = Y[3] - dx;
    if(nx != X[0] || ny != Y[0]) continue;

    ok = 1;
    writer(X[3], ' '); writer(Y[3],'\n');
    break;
    
  }while(next_permutation(d,d+3));

  if(!ok) writer(-1,'\n');

  return 0;
}

Current time: 2017年07月23日15時41分48秒
Last modified: 2014年12月23日23時06分09秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: