CSES - Aalto Competitive Programming 2024 - wk10 - Homework - Results
Submission details
Task:Line Segment Intersection
Sender:MallocManfred
Submission time:2024-11-07 00:56:09 +0200
Language:C++ (C++11)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.30 sdetails
#2ACCEPTED0.36 sdetails
#3ACCEPTED0.45 sdetails
#4ACCEPTED0.54 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vout(x) for(int i=0;i<(long long)x.size();i++) printf("%lld ",x[i]);
#define REP(i,a,b) for (int i = a; i <= b; i++)
// g++ <filename>.cpp -g -Wall -Wextra -DDEBUG -o <executable>
// copied from: https://codeforces.com/blog/entry/79024
// === Debug macro starts here ===
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v){
os<<"[";
for(auto& x:v){os<<x<<", ";}
return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p){
return os<<"{"<<p.first<<", "<<p.second<<"}";
}
// === Debug macro ends here ===
struct pt {
long long x, y;
pt operator +(const pt &p) const {return pt{x + p.x, y + p.y};}
pt operator -(const pt &p) const {return pt{x - p.x, y - p.y};}
bool operator ==(const pt &p) {return x == p.x && y == p.y;}
long long operator *(const pt &p) const {return x * p.y - y * p.x;}
void print() {cout << "[" << x << "," << y << "]\n";}
long long cross(const pt &a, const pt &b) const {
return (a - *this) * (b - *this);
}
};
void intersect(pt p1, pt p2, pt p3, pt p4) {
// parallel
if ((p2 - p1) * (p4 - p3) == 0) {
if(p1.cross(p2, p3) == 0)
{
for(int i = 0; i < 2; i++)
{
if(max(p1.x, p2.x) < min(p3.x, p4.x) || max(p1.y, p2.y) < min(p3.y, p4.y)){
printf("NO\n");
return;
}
swap(p1, p3);
swap(p2, p4);
}
printf("YES\n");
return;
}
}
// touching intersection
if (p1 == p3 || p1 == p4 || p2 == p3 || p2 == p4) {
cout << "YES\n";
return;
}
// general intersection
for (int i = 0; i < 2; i++) {
int s1 = p1.cross(p2, p3);
int s2 = p1.cross(p2, p4);
if((s1 < 0 && s2 < 0) || (s1 > 0 && s2 > 0))
{
printf("NO\n");
return;
}
swap(p1, p3);
swap(p2, p4);
}
cout << "YES\n";
return;
}
signed main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
pt p1,p2,p3,p4;
cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y>>p4.x>>p4.y;
intersect(p1,p2,p3,p4);
}
return 0;
}

Test details

Test 1

Verdict: ACCEPTED

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