結果
問題 | No.245 貫け! |
ユーザー |
![]() |
提出日時 | 2016-05-03 00:28:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 3,235 bytes |
コンパイル時間 | 1,766 ms |
コンパイル使用メモリ | 170,348 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-05 02:45:56 |
合計ジャッジ時間 | 2,681 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#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 methodstatic 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; }static int ccw(const Pt &a, const Pt &b) {double area = cross(a, b);if (area > 0) return 1; // counter clockwiseif (area < 0) return -1; // clockwisereturn 0; // on line}};template<typename T>Pt<T> operator*(double r, const Pt<T> &p) { return p*r; }template <typename T>void make_unique(std::vector<T> &vec) {std::sort(vec.begin(), vec.end());vec.erase(unique(vec.begin(), vec.end()), vec.end());}class GoThrough{public:void solve(void){int N;cin>>N;typedef Pt<double> Point;vector<pair<Point,Point>> line;vector<Point> points;REP(i,N){Point p,q;cin>>p.x>>p.y>>q.x>>q.y;line.emplace_back(p,q);points.push_back(p);points.push_back(q);}make_unique(points);int n = points.size();// 端点を通る直線を総当たりすればよい// O(N^3)//int ret = 1; // 少なくとも1つはそんざいするREP(i,n)FOR(j,i+1,n){Point p,q;p = points[i];q = points[j];int cnt = 0;REP(k,N){Point u,v;tie(u,v) = line[k];if ( Point::ccw(p-q, u-q) * Point::ccw(p-q, v-q) <= 0 )++cnt;}ret = max(ret,cnt);}cout<<ret<<endl;}};#if 1int main(int argc, char *argv[]){ios::sync_with_stdio(false);auto obj = new GoThrough();obj->solve();delete obj;return 0;}#endif