結果
問題 | No.199 星を描こう |
ユーザー |
![]() |
提出日時 | 2016-01-10 22:00:41 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 4,621 bytes |
コンパイル時間 | 1,653 ms |
コンパイル使用メモリ | 174,584 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-30 03:43:57 |
合計ジャッジ時間 | 2,624 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; template<typename T> struct Pt { T x, y; Pt(T x0, T y0) : x(x0), y(y0) {} Pt() :x(0),y(0) {} const Pt operator+(const Pt &other) const { return Pt(x+other.x, y+other.y); } const Pt operator-(const Pt &other) const { return Pt(x-other.x, y-other.y); } Pt &operator+=(const Pt &other) { x += other.x; y += other.y; return *this; } Pt &operator-=(const Pt &other) { x -= other.x; y -= other.y; return *this; } Pt operator*(double r) const { return Pt(x*r, y*r); } bool operator<(const Pt &other) const { return (x < other.x)? true : ((x==other.x)? (y < other.y) : false); } bool operator<=(const Pt &other) const { return (*this == other)? true : (*this < other); } bool operator>(const Pt &other) const { return (other < *this); } bool operator>=(const Pt &other) const { return (other <= *this); } bool operator==(const Pt &other) const { return (x==other.x && y==other.y); } bool operator!=(const Pt &other) const { return !(operator==(other)); } double norm(void) const { return hypot(x, y); } // class method static double cross(const Pt &a, const Pt &b) { return ((double)a.y*b.x - (double)a.x*b.y); } static double dot(const Pt &a, const Pt &b) { return (double)a.x*b.x+(double)a.y*b.y; } friend std::ostream &operator<<(std::ostream &os, const Pt &p) { os <<"("<<p.x<<","<<p.y<<")"; return os; } // a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定 static bool intersect(Pt a1, Pt a2, Pt b1, Pt b2) { return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < DBL_EPSILON ) && ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < DBL_EPSILON ); } static int ccw(const Pt &a, const Pt &b) { double area = cross(a, b); if (area > 0) return 1; // counter clockwise if (area < 0) return -1; // clockwise return 0; // on line } }; template<typename T> Pt<T> operator*(double r, const Pt<T> &p) { return p*r; } typedef Pt<double> Ptd; class WriteStars { public: void solve(void) { vector<Ptd> verts(5); REP(i,5) { int x,y; cin>>x>>y; verts[i] = Ptd(x,y); } sort(RANGE(verts)); // O(5!*5*5) do { vector<pair<Ptd,Ptd>> edges; REP(i,5) edges.push_back(make_pair(verts[i], verts[(i+1)%5])); int cnt = 0; REP(i,5) { auto e = edges[i]; Ptd p1,p2; tie(p1,p2) = e; set<Ptd> left; set<Ptd> right; REP(j,5) { if (i == j) continue; Ptd q1,q2; tie(q1,q2) = edges[j]; if (p1 == q1 || p1 == q2 || p2 == q1 || p2 == q2) continue; // 線分 e と交差するもののうち端点を left/right に振り分ける if ( !Ptd::intersect(p1,p2,q1,q2) ) continue; int ccw1 = Ptd::ccw(p2-p1,q1-p1); int ccw2 = Ptd::ccw(p2-p1,q2-p1); if ( ccw1 == 0 || ccw2 == 0 ) continue; if ( ccw1 > 0 ) { left.insert(q1); right.insert(q2); } else { left.insert(q2); right.insert(q1); } } if (left.size() == 1 || right.size() == 1) ++cnt; } if (cnt == 5) { cout<<"YES"<<endl; return; } } while(next_permutation(RANGE(verts))); cout<<"NO"<<endl; } }; #if 1 int main(int argc, char *argv[]) { ios::sync_with_stdio(false); auto obj = new WriteStars(); obj->solve(); delete obj; return 0; } #endif