CSES - Aalto Competitive Programming 2024 - wk10 - Homework - Results
Submission details
Task:Line Segment Intersection
Sender:Niilo
Submission time:2024-11-07 09:25:02 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.40 sdetails
#2ACCEPTED0.46 sdetails
#3ACCEPTED0.56 sdetails
#4ACCEPTED0.64 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails

Code

#include <iostream>
#include <cmath>
#include <vector>
#include <cassert>
using namespace std;
#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
constexpr double PI = 3.14159265358979323846;
template<class T>
struct Vec {
T x, y;
Vec() : x(0), y(0) {}
Vec(T x, T y) : x(x), y(y) {}
Vec operator+(Vec o) const { return Vec(x+o.x,y+o.y); }
Vec operator-(Vec o) const { return Vec(x-o.x,y-o.y); }
Vec operator*(Vec o) const { return Vec(x*o.x,y*o.y); }
Vec operator/(Vec o) const { return Vec(x/o.x,y/o.y); }
Vec operator+(T o) const { return Vec(x+o,y+o); }
Vec operator-(T o) const { return Vec(x-o,y-o); }
Vec operator*(T o) const { return Vec(x*o,y*o); }
Vec operator/(T o) const { return Vec(x/o,y/o); }
Vec operator-() const { return Vec(-x,-y); }
explicit operator bool() const { return x||y; }
bool operator==(Vec o) const { return x==o.x&&y==o.y; }
bool operator!=(Vec o) const { return x!=o.x||y!=o.y; }
bool operator<(Vec o) const { return x<o.x||(x==o.x&&y<o.y); }
bool operator>(Vec o) const { return o<*this; }
bool operator<=(Vec o) const { return x<o.x||(x==o.x&&y<=o.y); }
bool operator>=(Vec o) const { return o<=*this; }
void operator+=(Vec o) { x+=o.x;y+=o.y; }
void operator-=(Vec o) { x-=o.x;y-=o.y; }
void operator*=(Vec o) { x*=o.x;y*=o.y; }
void operator/=(Vec o) { x/=o.x;y/=o.y; }
void operator+=(T o) { x+=o;y+=o; }
void operator-=(T o) { x-=o;y-=o; }
void operator*=(T o) { x*=o;y*=o; }
void operator/=(T o) { x/=o;y/=o; }
T dot(Vec o) const { return x*o.x + y*o.y; }
/** left > 0, right < 0, same/opposite = 0 */
T cross(Vec o) const { return x*o.y - y*o.x; }
/** more left = bigger */
T rightturn(Vec o) const {
T d = dot(o), c = cross(o);
return d < 0 ? copysign(d-1,c) : c;
}
T len2() const { return x*x + y*y; };
T len() const { return sqrt(x*x + y*y); };
Vec norm() const { return *this * (1 / len()); }
/** 90deg counterclockwise/left */
Vec perp() const { Vec(-y, x); }
/** counterclockwise/left in radians */
Vec rot(T a) const { const T sa = sin(a), ca = cos(a); return Vec(x*ca - y*sa, x*sa + y*ca); }
friend istream& operator>>(istream& is, Vec& o) { return cin >> o.x >> o.y; }
friend ostream& operator<<(ostream& os, Vec o) { return cout << '(' << o.x << ',' << o.y << ')'; }
};
using pd = Vec<double>;
double polygonArea(const vector<pd>& p) {
assert(sz(p) >= 3);
double sum = p.back().cross(p.front());
rep(i,1,sz(p)) {
sum += p[i-1].cross(p[i]);
}
return abs(sum)/2;
}
bool pointIntersect(pd p1, pd p2, pd p3, pd p4) {
if (p2<p1) swap(p1,p2);
if (p4<p3) swap(p3,p4);
double c1 = (p1-p3).cross(p2-p3);
double c2 = (p1-p4).cross(p2-p4);
double c3 = (p3-p1).cross(p4-p1);
double c4 = (p3-p2).cross(p4-p2);
if (c1 == 0) return p1<=p3 && p3<=p2;
if (c2 == 0) return p1<=p4 && p4<=p2;
if (c3 == 0) return p3<=p1 && p1<=p4;
if (c4 == 0) return p3<=p2 && p2<=p4;
return (c1<0) != (c2<0) && (c3<0) != (c4<0);
}
int main() {
int n;
cin >> n;
rep(i,0,n) {
pd p1, p2, p3, p4;
cin >> p1 >> p2 >> p3 >> p4;
cout << (pointIntersect(p1,p2,p3,p4) ? "YES\n" : "NO\n");
}
}

Test details

Test 1

Verdict:

input
100000
9 7 1 8 8 -5 0 2
10 1 -1 2 -4 1 -7 3
10 2 -8 6 1 2 2 -1
-10 1 9 -7 4 -3 -5 0
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...
Truncated

Test 2

Verdict: ACCEPTED

input
100000
81 745 -967 768 -451 -490 -454...

correct output
NO
NO
YES
NO
YES
...

user output
NO
NO
YES
NO
YES
...
Truncated

Test 3

Verdict: ACCEPTED

input
100000
492853 -452834 -657156 -282543...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...
Truncated

Test 4

Verdict: ACCEPTED

input
100000
788522666 939776556 -831492125...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...
Truncated

Test 5

Verdict: ACCEPTED

input
1
1 6 6 6 4 4 1000000000 1000000...

correct output
YES

user output
YES

Test 6

Verdict: ACCEPTED

input
1
-1000000000 1000000000 9999999...

correct output
NO

user output
NO