Task: | Line Segment Intersection |
Sender: | HFalke |
Submission time: | 2024-11-08 01:00:09 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.08 s | details |
#2 | ACCEPTED | 0.09 s | details |
#3 | ACCEPTED | 0.11 s | details |
#4 | ACCEPTED | 0.13 s | details |
#5 | WRONG ANSWER | 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 writingtypedef 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 valuesconst 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 optimizationios::sync_with_stdio(0);cin.tie(0);//Input definitionll n;//Read Incin >> n;po tests[n][4];ll x;ll y;REP(i,0,n){REP(j,0,4){cin >> x >> y;tests[i][j] = {x,y};}}//Main partvector<bool> res(n,false);po a;po b;po c;po d;REP(i,0,n){//Quicker Writinga = tests[i][0];b = tests[i][1];c = tests[i][2];d = tests[i][3];//First case:if(cross(c-a,c-b) == 0 && cross(d-a,d-b) == 0){if(between(a,b,c) || between(a,b,d)){res[i] = true;continue;}}//Second case:if ((a==c) || (b==c) || (a==d) || (b==d)){res[i] = true;continue;}//Third case:if(((cross(c-a,c-b) > 0 && cross(d-a,d-b) < 0) ||(cross(c-a,c-b) < 0 && cross(d-a,d-b) > 0)) &&((cross(a-c,a-d) > 0 && cross(b-c,b-d) < 0) ||(cross(a-c,a-d) < 0 && cross(b-c,b-d) > 0 ))){res[i] = true;}}//Write outREP(i,0,n){cout << (res[i] ? "YES" : "NO") << "\n";}//Returnreturn 0;}
Test details
Test 1
Verdict: WRONG ANSWER
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: WRONG ANSWER
input |
---|
1 1 6 6 6 4 4 1000000000 1000000... |
correct output |
---|
YES |
user output |
---|
NO |
Test 6
Verdict: ACCEPTED
input |
---|
1 -1000000000 1000000000 9999999... |
correct output |
---|
NO |
user output |
---|
NO |