結果

問題 No.199 星を描こう
ユーザー たこしたこし
提出日時 2015-06-09 20:59:28
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,567 bytes
コンパイル時間 766 ms
コンパイル使用メモリ 96,248 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-28 18:39:48
合計ジャッジ時間 1,830 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define INF_MIN 100000000
#define INF 1145141919
#define INF_MAX 2147483647
#define LL_MAX 9223372036854775807
#define EPS 1e-10
#define PI acos(-1)
#define LL long long

using namespace std;

/*********************************************************

幾何ライブラリ

点を表すクラス
・Point
ベクトルを表すクラス
・Vector
線分を表すクラス
・Segment
直線を表すクラス
・Line
円を表すクラス
・Circle
多角形を表すクラス
・Polygon

内積を返す関数
・double dot(Vector a, Vector b)

外積の大きさ
・double cross(Vector a, Vector b)

線分ｓに対して、点Pから引いた垂線との交点の座標
・Point project(Line s, Point p)

線分sを対称軸とした点ｐの線対称の点
・Point reflect(Segment s, Point p)

線分po->p1に対してp2はp0を基準にどの方向に回転させたか
・int ccw(Point p0, Point p1, Point p2)

二つの線分の交差判定
・bool intersect(Segment s1, Segment s2)

二点の距離
・double getDistancePP(Point a, Point b)

直線lと点pの距離
・double getDistanceLP(Line l, Point p)

線分sと点pの距離
・double getDistanceSP(Segment s, Point p)

線分と線分の距離
・double getDistanceSS(Segment s1, Segment s2)

線分と線分の交点
・Point getCrossPoint(Segment s1, Segment s2)

円C1とC2の交点を求める(交差しない場合は判定しない)
・pair<Point, Point> getCrossPoints(Circle c1, Circle c2)

円Cと線分lの交点(交点を持たない場合は判定しない)
・pair<Point, Point> getCrossPoints(Circle c, Line l)

多角形gの中に点pが含まれているかどうか(IN, OUT, ON)
・int contains(Polygon g, Point p)

凸法(直線上にある点もすべて反時計周りに列挙する)
・Polygon andrewScan(Polygon s)

*********************************************************/


const double mEPS = 1e-10;

//点をあらわすクラス
class Point{
public:
  double x, y;

  Point(double x = 0.0, double y = 0.0) : x(x), y(y){}

  Point operator + (Point p){ return Point(x + p.x, y + p.y); }
  Point operator - (Point p){ return Point(x - p.x, y - p.y); }
  Point operator * (double a){ return Point(a*x, a*y); }
  Point operator / (double a){ return Point(x / a, y / a); }

  double abs(){ return sqrt(norm()); } //距離
  double norm(){ return x*x + y*y; }

  bool operator < (const Point &p) const{
    return x != p.x ? x < p.x : y < p.y;
  }

  //EPSは十分小さな値
  bool operator == (const Point &p) const {
    return fabs(x - p.x) < mEPS && fabs(y - p.y) < mEPS;
  }

};

class Segment{
public:
  Point p1, p2;
};

class Circle{
public:
  Point c;
  double r;
};

typedef vector<Point> Polygon;

//点を線として扱う
typedef Point Vector;
//線分を直線として扱う
typedef Segment Line;

//内積
double dot(Vector a, Vector b){
  return a.x*b.x + a.y*b.y;
}

//外積の大きさ
double cross(Vector a, Vector b){
  return a.x*b.y - a.y*b.x;
}

//線分ｓに対して、点Pから引いた垂線との交点の座標
Point project(Line s, Point p){
  Vector base = s.p2 - s.p1;
  double r = dot(p - s.p1, base) / base.norm();
  return s.p1 + base*r;
}

//線分sを対称軸とした点ｐの線対称の点
Point reflect(Segment s, Point p){
  return p + (project(s, p) - p) * 2.0;
}

//線分po->p1に対してp2はp0を基準にどの方向に回転させたか
int ccw(Point p0, Point p1, Point p2){

  //p0->p1をp0始点、p1終点の基準ベクトルとしたとき

  //p0->p2が反時計回りになるとき
  static const int COUNTER_CLOCKWISE = 1;
  //p0->p2が時計回りになるとき
  static const int CLOCKWISE = -1;
  //p2,p0,p1の順で同一直線上にあるとき
  static const int ONLINE_BACK = 2;
  //p0,p1,p2 の順で同一直線上にある場合
  static const int ONLINE_FRONT = -2;
  //p2 が線分 p0p1 上にある場合
  static const int ON_SEGMENT = 0;

  Vector a = p1 - p0;
  Vector b = p2 - p0;

  if (cross(a, b) > mEPS) return COUNTER_CLOCKWISE;
  if (cross(a, b) < -mEPS) return CLOCKWISE;
  if (dot(a, b) < -mEPS) return ONLINE_BACK;
  if (a.norm() < b.norm()) return ONLINE_FRONT;

  return ON_SEGMENT;

}

//二つの線分の交差判定
bool intersect(Segment s1, Segment s2){
  return(ccw(s1.p1, s1.p2, s2.p1) * ccw(s1.p1, s1.p2, s2.p2) < 0 &&
	 ccw(s2.p1, s2.p2, s1.p1) * ccw(s2.p1, s2.p2, s1.p2) < 0);
}

Point mPoint[5];

int main(){

  vector<int> List;

  for(int i = 0; i < 5; i++){
    cin >> mPoint[i].x >> mPoint[i].y;
    List.push_back(i);
  }

  do{

    int pos = 0;
    int next = 1;

    Segment mSeg[5];

    while(true){
      
      mSeg[pos].p1 = mPoint[List[pos]];
      mSeg[pos].p2 = mPoint[List[next]];

      if(pos + 1 == 5)
	break;

      pos = (pos + 1) % 5;
      next = (next + 1) % 5;

    }

    bool ans = true;

    for(int n = 0; n < 5; n++){
      if(!intersect(mSeg[n], mSeg[(n+2)%5]) || !intersect(mSeg[n], mSeg[(n+3)%5])){
	ans = false;
	break;
      }
    }

    if(ans){
      cout << "YES" << endl;
      return 0;
    }

  }while(next_permutation(List.begin(), List.end()));

  cout << "NO" << endl;

  return 0;

}
0