#31571 (C++11) No.199 星を描こう

提出ソース

結果

問題	No.199 星を描こう
ユーザー	たこし
提出日時	2015-06-09 20:59:28
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	5,567 bytes
コンパイル時間	837 ms
コンパイル使用メモリ	96,644 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-09 13:51:09
合計ジャッジ時間	1,726 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	1 ms 6,944 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	1 ms 6,944 KB
testcase_12	AC	1 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	1 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	1 ms 6,944 KB
testcase_20	AC	2 ms 6,944 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	1 ms 6,940 KB
testcase_25	AC	1 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	1 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;

}

yukicoder

結果

テストケース

ソースコード