Submission #117141
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <list>
#include <cassert>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define EPS 1e-9
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
struct P {
typedef int T; typedef ll T2; //T2は{a*b | a:T, b:T}を含むタイプ
T x, y;
P(T x_, T y_): x(x_), y(y_) {}
P(): x(0), y(0) {}
};
inline bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; }
inline bool operator<(const P& a, const P& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
inline P operator+(const P& a, const P& b) { return P(a.x+b.x, a.y+b.y); }
inline P operator-(const P& a, const P& b) { return P(a.x-b.x, a.y-b.y); }
inline P operator-=(P& a, const P& b) { a.x -= b.x, a.y -= b.y ; return a; }
inline P::T2 cross(const P& a, const P& b) { return (P::T2)a.x*b.y - (P::T2)a.y*b.x; }
inline P::T2 dot(const P& a, const P& b) { return (P::T2)a.x*b.x + (P::T2)a.y*b.y; }
inline P::T2 norm(const P& a) { return (P::T2)a.x*a.x + (P::T2)a.y*a.y; }
ostream& operator<<(ostream& out, const P& x) { out << "(" << x.x << ", " << x.y << ")"; return out; }
struct L {
P a, b;
L(const P &a_, const P &b_): a(a_), b(b_) {}
const P& operator[](size_t i) const { return i ? b : a; }
};
inline int ccw(const P& a, const P& b, const P& c) {
int ax = b.x - a.x, ay = b.y - a.y, bx = c.x - a.x, by = c.y - a.y;
P::T2 t = (P::T2)ax*by - (P::T2)ay*bx;
if (t > 0) return 1;
if (t < 0) return -1;
if((P::T2)ax*bx + (P::T2)ay*by < 0) return +2;
if((P::T2)ax*ax + (P::T2)ay*ay < (P::T2)bx*bx + (P::T2)by*by) return -2;
return 0;
}
int intersectSS(const L &s, const L &t) {
int a = ccw(s.a,s.b,t.a), b = ccw(s.a,s.b,t.b), c = ccw(t.a,t.b,s.a), d = ccw(t.a,t.b,s.b);
int x = a * b, y = c * d;
if(x == -1 && y == -1) return 0; //cross
else if(
((abs(b) == 1 || b == -2) && s.b == t.a) ||
((abs(b) == 1 || b == 2) && s.a == t.a) ||
((abs(a) == 1 || a == -2) && s.b == t.b) ||
((abs(a) == 1 || a == 2) && s.a == t.b)
) return 2; // point overlap (真ん中と端を共有する)
else if(
(x == 0 && (abs(a) + abs(b) == 1)) ||
(y == 0 && (abs(c) + abs(d) == 1))
) return 3; // point overlap (端点のみを共有する)
else if(x <= 0 && y <= 0) return 0; //segment overlap
else return 1;
}
int main() {
int N, NX, NY, QX, QY;
cin >> N >> NX >> NY >> QX >> QY;
L seg(P(NX, NY), P(QX, QY));
int r = 1;
rep(i, N-1) {
int ax, ay, bx, by;
cin >> ax >> ay >> bx >> by;
L s(P(ax, ay), P(bx, by));
if(intersectSS(seg, s) != 1)
r ++;
}
cout << r << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 白蛇のお守り |
User |
anta |
Language |
C++ (G++ 4.6.4) |
Score |
100 |
Code Size |
3652 Byte |
Status |
AC |
Exec Time |
39 ms |
Memory |
920 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00-sample, 10-parallel, 10-retmin, 10-touch, 50-alignedrand-00, 50-alignedrand-01, 50-alignedrand-02, 50-alignedrand-03, 50-alignedrand-04, 50-alignedrand-05, 50-alignedrand-06, 50-alignedrand-07, 50-random-00, 50-random-01, 50-random-02, 50-random-03, 50-random-04, 50-random-05, 50-random-06, 50-random-07, 50-random-08, 50-random-09, 50-random-10, 50-random-11, 50-random-12, 50-random-13, 50-random-14, 50-random-15, 50-random-16, 50-random-17, 50-random-18, 50-random-19, 50-random-20, 50-random-21, 50-random-22, 50-random-23, 50-random-24, 50-retmax-00, 50-retmax-01, 50-retmax-02, 50-retmin-00, 50-retmin-01, 50-retmin-02 |
Case Name |
Status |
Exec Time |
Memory |
00-sample |
AC |
22 ms |
796 KB |
10-parallel |
AC |
22 ms |
920 KB |
10-retmin |
AC |
22 ms |
796 KB |
10-touch |
AC |
22 ms |
912 KB |
50-alignedrand-00 |
AC |
36 ms |
804 KB |
50-alignedrand-01 |
AC |
26 ms |
788 KB |
50-alignedrand-02 |
AC |
36 ms |
720 KB |
50-alignedrand-03 |
AC |
27 ms |
792 KB |
50-alignedrand-04 |
AC |
28 ms |
792 KB |
50-alignedrand-05 |
AC |
26 ms |
800 KB |
50-alignedrand-06 |
AC |
28 ms |
784 KB |
50-alignedrand-07 |
AC |
37 ms |
796 KB |
50-random-00 |
AC |
36 ms |
804 KB |
50-random-01 |
AC |
36 ms |
792 KB |
50-random-02 |
AC |
34 ms |
788 KB |
50-random-03 |
AC |
36 ms |
788 KB |
50-random-04 |
AC |
29 ms |
796 KB |
50-random-05 |
AC |
34 ms |
788 KB |
50-random-06 |
AC |
29 ms |
796 KB |
50-random-07 |
AC |
31 ms |
796 KB |
50-random-08 |
AC |
33 ms |
788 KB |
50-random-09 |
AC |
35 ms |
792 KB |
50-random-10 |
AC |
35 ms |
796 KB |
50-random-11 |
AC |
28 ms |
796 KB |
50-random-12 |
AC |
24 ms |
716 KB |
50-random-13 |
AC |
24 ms |
792 KB |
50-random-14 |
AC |
32 ms |
808 KB |
50-random-15 |
AC |
24 ms |
788 KB |
50-random-16 |
AC |
27 ms |
788 KB |
50-random-17 |
AC |
32 ms |
908 KB |
50-random-18 |
AC |
34 ms |
800 KB |
50-random-19 |
AC |
30 ms |
788 KB |
50-random-20 |
AC |
39 ms |
792 KB |
50-random-21 |
AC |
36 ms |
788 KB |
50-random-22 |
AC |
28 ms |
788 KB |
50-random-23 |
AC |
22 ms |
796 KB |
50-random-24 |
AC |
34 ms |
796 KB |
50-retmax-00 |
AC |
36 ms |
808 KB |
50-retmax-01 |
AC |
36 ms |
796 KB |
50-retmax-02 |
AC |
36 ms |
792 KB |
50-retmin-00 |
AC |
29 ms |
796 KB |
50-retmin-01 |
AC |
29 ms |
720 KB |
50-retmin-02 |
AC |
26 ms |
792 KB |