Task: | Line Segment Intersection |
Sender: | Niilo |
Submission time: | 2024-11-07 09:25:02 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.40 s | details |
#2 | ACCEPTED | 0.46 s | details |
#3 | ACCEPTED | 0.56 s | details |
#4 | ACCEPTED | 0.64 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
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: 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: 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 |