結果
| 問題 | No.245 貫け！ |
| ユーザー |
 しらっ亭
|
| 提出日時 | 2016-08-17 04:43:56 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,303 bytes |
| コンパイル時間 | 2,755 ms |
| コンパイル使用メモリ | 199,532 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-07 18:39:47 |
| 合計ジャッジ時間 | 3,599 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 2 ms
5,248 KB |
| testcase_04 | AC | 2 ms
5,248 KB |
| testcase_05 | AC | 2 ms
5,248 KB |
| testcase_06 | AC | 2 ms
5,248 KB |
| testcase_07 | WA | - |
| testcase_08 | AC | 2 ms
5,248 KB |
| testcase_09 | WA | - |
| testcase_10 | AC | 3 ms
5,248 KB |
| testcase_11 | AC | 5 ms
5,248 KB |
| testcase_12 | AC | 11 ms
5,248 KB |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | AC | 11 ms
5,248 KB |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define ALL(x) (x).begin(), (x).end()
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
#define fst first
#define snd second
typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> pii;typedef vector<pii> vpii;
typedef long long ll;
#define PI (3.14159265358979323846)
#define EPS (1e-7)
#define curr(P, i) P[(i) % P.size()]
#define next(P, i) P[(i+1) % P.size()]
#define prev(P, i) P[(i+P.size()-1) % P.size()]
#define diff(P, i) (next(P,i) - curr(P,i))
#define EQ(x,y) (fabs((x)-(y))<EPS)
#define GE(x,y) ((x)+EPS>(y))
#define LE(x,y) ((x)<(y)+EPS)
enum { OUT, ON, IN };
typedef complex<double> P;
typedef vector<P> G;
namespace std{
bool operator < (const P& a, const P& b) {
return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}
}
double cross(const P& a, const P& b) {
return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
return real(conj(a)*b);
}
struct L : public vector<P> {
L(){}
L(const P &a, const P &b) {
push_back(a); push_back(b);
}
};
struct C {
P p; double r;
C(const P &p, double r) : p(p), r(r) { }
};
int ccw(P a, P b, P c) {
b -= a; c -= a;
if (cross(b, c) > EPS) return +1; // counter clockwise
if (cross(b, c) < -EPS) return -1; // clockwise
if (dot(b, c) < -EPS) return +2; // c--a--b on line
if (norm(b) < norm(c)+EPS) return -2; // a--b--c on line
return 0;
}
bool intersectLL(const L &l, const L &m) {
return abs(cross(l[1]-l[0], m[1]-m[0])) > EPS || // non-parallel
abs(cross(l[1]-l[0], m[0]-l[0])) < EPS; // same line
}
bool intersectLS(const L &l, const L &s) {
return cross(l[1]-l[0], s[0]-l[0])* // s[0] is left of l
cross(l[1]-l[0], s[1]-l[0]) < EPS; // s[1] is right of l
}
bool intersectLP(const L &l, const P &p) {
return abs(cross(l[1]-p, l[0]-p)) < EPS;
}
bool intersectSS(const L &s, const L &t) {
return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
}
bool intersectSP(const L &s, const P &p) {
return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality
}
P projection(const L &l, const P &p) {
double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);
return l[0] + t*(l[0]-l[1]);
}
P reflection(const L &l, const P &p) {
return p + 2.0 * (projection(l, p) - p);
}
double distanceLP(const L &l, const P &p) {
return abs(p - projection(l, p));
}
double distanceLL(const L &l, const L &m) {
return intersectLL(l, m) ? 0 : distanceLP(l, m[0]);
}
double distanceLS(const L &l, const L &s) {
if (intersectLS(l, s)) return 0;
return min(distanceLP(l, s[0]), distanceLP(l, s[1]));
}
double distanceSP(const L &s, const P &p) {
const P r = projection(s, p);
if (intersectSP(s, r)) return abs(r - p);
return min(abs(s[0] - p), abs(s[1] - p));
}
double distanceSS(const L &s, const L &t) {
if (intersectSS(s, t)) return 0;
return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),
min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}
P crossP(const L &l, const L &m) {
double A = cross(l[1] - l[0], m[1] - m[0]);
double B = cross(l[1] - l[0], l[1] - m[0]);
if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
return m[0] + B / A * (m[1] - m[0]);
}
vector<P> crossPLC(const L &l, const C &c){
vector<P> res;
P p = projection(l, c.p);
double d1 = abs(p - c.p);
if(EQ(d1, c.r)){
res.push_back(p);
return res;
}
if(d1 > c.r){
return res;
}
double d2 = sqrt(c.r*c.r - d1*d1);
P v = d2/abs(l[1] - l[0]) * (l[1] - l[0]);
res.push_back(p + v);
res.push_back(p - v);
return res;
}
#define sq(x) ((x)*(x))
vector<P> crossPCC(const C &c1, const C &c2){
vector<P> res;
P v = c2.p - c1.p;
double d = abs(v);
if(d < EPS){
if(EQ(c1.r, c2.r)){ // coincide
res.push_back(c1.p + P(c1.r, 0));
}
return res;
}
vector<double> thetas;
if(EQ(d, c1.r + c2.r)){
thetas.push_back(0);
}else if(EQ(d, c1.r - c2.r)){
thetas.push_back(0);
}else if(EQ(d, c2.r - c1.r)){
thetas.push_back(PI);
}else if(d > c1.r + c2.r || d < abs(c1.r - c2.r)){
return res;
}else{
double t = acos((sq(c1.r) + sq(d) - sq(c2.r))
/ (2.0 * c1.r * d));
thetas.push_back(t);
thetas.push_back(-t);
}
for (int i=0; i < (int) thetas.size(); i++){
res.push_back(c1.p + c1.r/d * v
* P(cos(thetas[i]), sin(thetas[i])));
}
return res;
}
vector<L> tangentPC(const P& p, const C& c){
vector<L> res;
P v = c.p - p;
double d1 = abs(v), d2;
if(EQ(d1, c.r)){
d2 = sqrt(sq(d1) - sq(c.r));
P q = p + v * P(cos(PI/2.0), sin(PI/2.0));
res.push_back(L(q, p));
return res;
}else if(d1 < c.r){
return res;
}else{
d2 = sqrt(sq(d1) - sq(c.r));
double t = atan2(c.r, d2);
P q = p + d2/d1 * v * P(cos(t), sin(t));
res.push_back(L(p, q));
q = p + d2/d1 * v * P(cos(-t), sin(-t));
res.push_back(L(p, q));
return res;
}
}
vector<L> commontangentCC(const C& c1, const C& c2){
vector<L> res;
P v = c2.p - c1.p;
double d = abs(v);
if(d < EPS){
if(EQ(c1.r, c2.r)){ // coinside
P q1 = c1.p + P(c1.r, 0);
P q2 = q1 + P(0, c1.r);
res.push_back(L(q1, q2));
}
return res;
}
if(d + EPS <= abs(c1.r - c2.r)){
return res;
}else if(EQ(d, c1.r - c2.r)){
P q1 = c1.r/d * v;
P q2 = q1 + v * P(cos(PI/2.0), sin(PI/2.0));
res.push_back(L(q1, q2));
return res;
}else if(EQ(d, c2.r - c1.r)){
P q1 = c2.r/d * -v;
P q2 = q1 + v * P(cos(PI/2.0), sin(PI/2.0));
res.push_back(L(q1, q2));
return res;
}else{
double t1 = asin((c2.r - c1.r)/d) + PI/2.0;
P q1 = c1.p + c1.r/d * v * P(cos(t1), sin(t1));
P q2 = c2.p + c2.r/d * v * P(cos(t1), sin(t1));
res.push_back(L(q1, q2));
q1 = c1.p + c1.r/d * v * P(cos(-t1), sin(-t1));
q2 = c2.p + c2.r/d * v * P(cos(-t1), sin(-t1));
res.push_back(L(q1, q2));
if(d + EPS <= c1.r + c2.r){
return res;
}else if(EQ(d, c1.r + c2.r)){
P q3 = c1.p + c1.r/d * v;
P q4 = q3 + v * P(cos(PI/2.0), sin(PI/2.0));
res.push_back(L(q3, q4));
}else{
double t2 = acos((c1.r + c2.r)/d);
P q3 = c1.p + c1.r/d * v * P(cos(t2), sin(t2));
P q4 = c2.p - c2.r/d * v * P(cos(t2), sin(t2));
res.push_back(L(q3, q4));
q3 = c1.p + c1.r/d * v * P(cos(-t2), sin(-t2));
q4 = c2.p - c2.r/d * v * P(cos(-t2), sin(-t2));
res.push_back(L(q3, q4));
}
}
return res;
}
vector<C> tangentcircleLL(const L& l, const L& m, const double& r){
vector<C> res;
if(abs(cross(l[1]-l[0], m[1]-m[0])) < EPS){ // parallel
double d = distanceLL(l, m);
if(EQ(d, r*2.0)){
P p = P(l[0] + r/abs(l[1]-l[0]) * (l[1]-l[0])
* P(cos(PI/2), sin(PI/2)));
res.push_back(C(p, r));
}
return res;
}
P p = crossP(l, m);
double t1 = (arg(m[1]-m[0]) - arg(l[1]-l[0])) / 2.0;
P v1 = abs(r/sin(t1)) / abs(l[1]-l[0]) * (l[1]-l[0])
* P(cos(t1), sin(t1));
double t2 = PI/2 - t1;
P v2 = abs(r/sin(t2)) / abs(m[1]-m[0]) * (m[1]-m[0])
* P(cos(t2), sin(t2));
res.push_back(C(p + v1, r));
res.push_back(C(p + v2, r));
res.push_back(C(p - v1, r));
res.push_back(C(p - v2, r));
return res;
}
#undef sq
int contains(const G& g, const P& p) {
bool in = false;
for (int i = 0; i < (int) g.size(); ++i) {
P a = curr(g,i) - p, b = next(g,i) - p;
if (imag(a) > imag(b)) swap(a, b);
if (imag(a) <= 0 && 0 < imag(b))
if (cross(a, b) < 0) in = !in;
if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
}
return in ? IN : OUT;
}
#define d(k) (dot(p[k], l[1] - l[0]))
P extreme(const vector<P> &p, const L &l) {
int k = 0;
for (int i = 1; i < (int) p.size(); ++i)
if (d(i) > d(k)) k = i;
return p[k];
}
#undef d
double area2(const G& p) {
double A = 0;
for (int i = 0; i < (int) p.size(); ++i)
A += cross(curr(p, i), next(p, i));
return A;
}
vector<P> convex_hull(vector<P> ps) {
int n = ps.size(), k = 0;
sort(ps.begin(), ps.end());
vector<P> ch(2*n);
for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
ch.resize(k-1);
return ch;
}
bool isconvex(const G &P) {
for (int i = 0; i < (int) P.size(); ++i)
if (ccw(prev(P, i), curr(P, i), next(P, i)) > 0) return false;
return true;
}
G convex_cut(const G& p, const L& l) {
G Q;
for (int i = 0; i < (int) p.size(); ++i) {
P A = curr(p, i), B = next(p, i);
if (ccw(l[0], l[1], A) != -1) Q.push_back(A);
if (ccw(l[0], l[1], A)*ccw(l[0], l[1], B) < 0)
Q.push_back(crossP(L(A, B), l));
}
return Q;
}
int convex_contains(const G &Q, const P &p) {
const int n = Q.size();
P g = (Q[0] + Q[n/3] + Q[2*n/3]) / 3.0; // inner-P
int a = 0, b = n;
while (a+1 < b) { // invariant: c is in fan g-Q[a]-Q[b]
int c = (a + b) / 2;
if (cross(Q[a]-g, Q[c]-g) > 0) { // angle < 180 deg
if (cross(Q[a]-g, p-g) > 0 && cross(Q[c]-g, p-g) < 0) b = c;
else a = c;
} else {
if (cross(Q[a]-g, p-g) < 0 && cross(Q[c]-g, p-g) > 0) a = c;
else b = c;
}
}
b %= n;
if (cross(Q[a] - p, Q[b] - p) < 0) return 0;
if (cross(Q[a] - p, Q[b] - p) > 0) return 2;
return 1;
}
bool intersect_1pt(const P& a, const P& b,
const P& c, const P& d, P &r) {
double D = cross(b - a, d - c);
if (EQ(D, 0)) return false;
double t = cross(c - a, d - c) / D;
double s = -cross(a - c, b - a) / D;
r = a + t * (b - a);
return GE(t, 0) && LE(t, 1) && GE(s, 0) && LE(s, 1);
}
G convex_intersect(const G &p, const G &Q) {
const int n = p.size(), m = Q.size();
int a = 0, b = 0, aa = 0, ba = 0;
enum { Pin, Qin, Unknown } in = Unknown;
G R;
do {
int a1 = (a+n-1) % n, b1 = (b+m-1) % m;
double C = cross(p[a] - p[a1], Q[b] - Q[b1]);
double A = cross(p[a1] - Q[b], p[a] - Q[b]);
double B = cross(Q[b1] - p[a], Q[b] - p[a]);
P r;
if (intersect_1pt(p[a1], p[a], Q[b1], Q[b], r)) {
if (in == Unknown) aa = ba = 0;
R.push_back( r );
in = B > 0 ? Pin : A > 0 ? Qin : in;
}
if (C == 0 && B == 0 && A == 0) {
if (in == Pin) { b = (b + 1) % m; ++ba; }
else { a = (a + 1) % m; ++aa; }
} else if (C >= 0) {
if (A > 0) { if (in == Pin) R.push_back(p[a]); a = (a+1)%n; ++aa; }
else { if (in == Qin) R.push_back(Q[b]); b = (b+1)%m; ++ba; }
} else {
if (B > 0) { if (in == Qin) R.push_back(Q[b]); b = (b+1)%m; ++ba; }
else { if (in == Pin) R.push_back(p[a]); a = (a+1)%n; ++aa; }
}
} while ( (aa < n || ba < m) && aa < 2*n && ba < 2*m );
if (in == Unknown) {
if (convex_contains(Q, p[0])) return p;
if (convex_contains(p, Q[0])) return Q;
}
return R;
}
double convex_diameter(const G &pt) {
const int n = pt.size();
int is = 0, js = 0;
for (int i = 1; i < n; ++i) {
if (imag(pt[i]) > imag(pt[is])) is = i;
if (imag(pt[i]) < imag(pt[js])) js = i;
}
double maxd = norm(pt[is]-pt[js]);
int i, maxi, j, maxj;
i = maxi = is;
j = maxj = js;
do {
if (cross(diff(pt,i), diff(pt,j)) >= 0) j = (j+1) % n;
else i = (i+1) % n;
if (norm(pt[i]-pt[j]) > maxd) {
maxd = norm(pt[i]-pt[j]);
maxi = i; maxj = j;
}
} while (i != is || j != js);
return maxd; /* farthest pair is (maxi, maxj). */
}
#define d(k) (dot(p[k], l[1] - l[0]))
P convex_extreme(const G &p, const L &l) {
const int n = p.size();
int a = 0, b = n;
if (d(0) >= d(n-1) && d(0) >= d(1)) return p[0];
while (a < b) {
int c = (a + b) / 2;
if (d(c) >= d(c-1) && d(c) >= d(c+1)) return p[c];
if (d(a+1) > d(a)) {
if (d(c+1) <= d(c) || d(a) > d(c)) b = c;
else a = c;
} else {
if (d(c+1) > d(c) || d(a) >= d(c)) a = c;
else b = c;
}
}
return P();
}
#undef d
void Main() {
int N;
scanf("%d", &N);
vector<L> segs(N);
rep(i, N) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
segs[i] = {{(double)x1, (double)y1}, {(double)x2, (double)y2}};
}
vi zo = {0, 1};
int ma = 0;
rep(i, N) rep(j, i+1, N) {
forr(k, zo) {
forr(l, zo) {
L line = {segs[i][k], segs[j][l]};
int cand = 0;
rep(m, N) {
if (intersectLS(line, segs[m])) {
cand++;
}
}
ma = max(ma, cand);
}
}
}
_p("%d\n", ma);
}
int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }