Task: | Line Segment Intersection |
Sender: | HFalke |
Submission time: | 2024-11-08 02:18:41 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.07 s | details |
#2 | ACCEPTED | 0.08 s | details |
#3 | WRONG ANSWER | 0.10 s | details |
#4 | WRONG ANSWER | 0.12 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
Code
#include <bits/stdc++.h> using namespace std; //Definitions for quicker writing #define REP(i,a,b) for (int i = a; i < b; i++) #define clz __builtin_clz #define ctz __builtin_ctz #define popct __builtin_popcount #define PB push_back #define MP make_pair #define F first #define S second #define X real() #define Y imag() //Typedefs for quicker writing typedef long long ll; typedef vector<int> vi; typedef vector<long long> vl; typedef pair<int,int> pi; typedef pair<long long, long long> pl; typedef complex<long long> po; //Max values const long long lmx = LLONG_MAX; const int imx = INT_MAX; ll cross(po v, po w){ return v.X * w.Y - v.Y * w.X; } //Is c between a and b? bool between(po a,po b,po c){ return c.X <= max(a.X,b.X) && c.X >= min(a.X,b.X) && c.Y <= max(a.Y,b.Y) && c.Y >= min(a.Y,b.Y); } int main() { //IO optimization ios::sync_with_stdio(0); cin.tie(0); //Input definition ll n; //Read In cin >> n; //Main part ll x,y; po a,b,c,d; bool res = false; REP(i,0,n){ cin >> x >> y; a = {x,y}; cin >> x >> y; b = {x,y}; cin >> x >> y; c = {x,y}; cin >> x >> y; d = {x,y}; //First case: //The lines are parallel and the segments overlap if(cross(b-a,d-c) == 0 && (cross(c-a,c-b) == 0 || cross(d-a,d-b) == 0)){ if(between(a,b,c) || between(a,b,d) || between(c,d,a) || between(c,d,b)){ res = true; } } //Second case: //Any of the points match if ((a==c) || (b==c) || (a==d) || (b==d)){ res = true; } //Third case: //Point location //a and b have to be on different sides //same goes for c and d ll c1 = cross(c-a,b-a); ll c2 = cross(d-a,b-a); ll c3 = cross(a-c,d-c); ll c4 = cross(b-c,d-c); if(c1*c2 < 0 && c3*c4 < 0){ res = true; } //Fourth case: //One of the endpoints is on one of the lines if(cross(c-a,c-b) == 0 && between(a,b,c)) res = true; if(cross(d-a,d-b) == 0 && between(a,b,d)) res = true; if(cross(a-c,a-d) == 0 && between(c,d,a)) res = true; if(cross(b-c,b-d) == 0 && between(c,d,b)) res = true; //Write out cout << (res ? "YES" : "NO") << "\n"; //Reset res = false; } //Return 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 ... |
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 ... |
Test 3
Verdict: WRONG ANSWER
input |
---|
100000 492853 -452834 -657156 -282543... |
correct output |
---|
YES YES NO YES YES ... |
user output |
---|
NO YES NO NO NO ... |
Test 4
Verdict: WRONG ANSWER
input |
---|
100000 788522666 939776556 -831492125... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
YES NO NO YES NO ... |
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 |