#37493 (C++11) No.245 貫け！

• 問題: No.245 貫け！
• ユーザー: ry0u_yd
• 提出日時: 2015-07-18 00:12:57
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 5,060 bytes
• コンパイル時間: 800 ms
• コンパイル使用メモリ: 90,948 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-07-08 09:49:29
• 合計ジャッジ時間: 1,639 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Point {
    double x, y;

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

    Point operator+(const Point &o) const { return Point(x+o.x, y+o.y); }

    Point operator-(const Point &o) const { return Point(x-o.x, y-o.y); }

    Point operator*(const double m) const { return Point(x*m, y*m); }

    Point operator/(const double d) const { return Point(x/d, y/d); }

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

    bool operator==(const Point &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }

    double cross(const Point &o) const { return x * o.y - y * o.x; }

    double dot(const Point &o) const { return x * o.x + y * o.y; }

    double atan() const { return atan2(y, x); }

    double norm() const { return sqrt(dot(*this)); }

    double distance(const Point &o) const { return (o - (*this)).norm(); }

    double area(const Point &a,const Point &b) {
        Point p = a - (*this), p2 = b - (*this); 
        return p.cross(p2);
    }

    double area_abs(const Point &a,const Point &b) const {
        Point p = a - (*this), p2 = b - (*this);
        return fabs(p.cross(p2)) / 2.0;
    }	

    //線分abが自身に含まれているのかどうか判断する
    int between(const Point &a,const Point &b) {
        if(area(a,b) != 0) return 0;

        if(a.x != b.x)  return ((a.x <= x) && (x <= b.x) || (a.x >= x) && (x >= b.x));
        else return ((a.y <= y) && (y <= b.y) || (a.y >= y) && (y >= b.y));
    }      

    double distance_seg(const Point& a,const Point& b) {
        if((b-a).dot(*this-a) < EPS) {
            return (*this-a).norm();
        }
        if((a-b).dot(*this-b) < EPS) {
            return (*this-b).norm();
        }
        return abs((b-a).cross(*this-a)) / (b-a).norm();
    }

    bool hitPolygon(const Point& a,const Point& b,const Point& c) {
        double t = (b-a).cross(*this-b);
        double t2 = (c-b).cross(*this-c);
        double t3 = (a-c).cross(*this-a);	

        if((t > 0 && t2 > 0 && t3 > 0) || ( t < 0 && t2 < 0 && t3 < 0)) {
            return true;
        }

        return false;
    }
};

struct Seg {
    Point a,b;

    Seg (Point a, Point b) : a(a),b(b) {}

    bool isOrthogonal(Seg &s) { return equals((b - a).dot(s.b - s.a),0.0); }

    bool isParallel(Seg &s) { return equals((b-a).cross(s.b - s.a),0.0); }

    bool isIntersect(Seg &s) {
        if(s.a.between(a,b) || s.b.between(a,b) || a.between(s.a,s.b) || b.between(s.a,s.b)) {
            return true;
        }
        return ((a-b).cross(s.a-a) * (a-b).cross(s.b-a) < EPS) && ((s.b-s.a).cross(a-s.a)*(s.b-s.a).cross(b-s.a) < EPS);
    }

    bool distance(Seg &s) {
        if((*this).isIntersect(s)) return 0.0;

        return min(min(a.distance_seg(s.a,s.b),b.distance_seg(s.a,s.b)),min(s.a.distance_seg(a,b),s.b.distance_seg(a,b)));
    }

    Point getCrossPoint(Seg &s) {
        Point p = s.b - s.a;
        double d = abs(p.cross(a-s.a));
        double d2 = abs(p.cross(b-s.a));

        double t = d / (d+d2);
        return a + (b-a)*t;
    }        

    bool operator<(const Seg &o) const { 
        return a == o.a ? a < o.a : b < o.b;
    }
};

struct event {
    double x;
    int type;
    Point a,b;

    event(double X,int T,Point A,Point B) {
        x = X;
        type = T;
        a = A;
        b = B;
    }

    bool operator < (const event &e) const {
        return x != e.x ? x > e.x : type > e.type;
    }
};


int main() {
    int n;
    cin >> n;

    vector<Seg> segs;

    rep(i,n) {
        double a,b,c,d;
        cin >> a >> b >> c >> d;

        Point p1(a,b);
        Point p2(c,d);

        segs.push_back(Seg(p1,p2));
    }


    priority_queue<event> Q;
    for (int i = 0; i < segs.size(); ++i) {
        double x1 = segs[i].a.x, x2 = segs[i].b.x;
        Q.push( event(min(x1,x2), 0, segs[i].a,segs[i].b) );
        Q.push( event(max(x1,x2), 1, segs[i].a,segs[i].b)  );
    }

    set<Seg> T;
    int count = 2;

    while (!Q.empty()) {
        event e = Q.top();
        Q.pop();
    
        Seg s(e.a,e.b);
        if (e.type == 0) {
            for (set<Seg>::iterator itr = T.begin(); itr != T.end(); ++itr) {
                Seg res = *itr;
                // cout << res.a.x << " " << res.a.y << " " << res.b.x << " " << res.b.y << endl;
                // cout << e.seg.a.x << " " << e.seg.a.y << " " << e.seg.b.x << " " << e.seg.b.y << endl;
                if(res.isIntersect(s)){
                    count++;
                }
            }
            T.insert(s);
        }
        else T.erase(s);
    }
    
    cout << count << endl;

    return 0;
}