Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- #define ll long long int
- //pair<> data structure can also be used instead of struct
- struct point{
- ll x,y;
- };
- struct segment{
- point s,e;
- };
- // Given three collinear points p, q, r, the function checks if
- // point q lies on line segment 'pr'
- bool onSegment(point p, point q, point r)
- {
- if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
- q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
- return true;
- return false;
- }
- // To find orientation of ordered triplet (p, q, r).
- // The function returns following values
- // 0 --> p, q and r are collinear
- // 1 --> Clockwise
- // 2 --> Counterclockwise
- int orientation(point p, point q, point r)
- {
- // See https://www.geeksforgeeks.org/orientation-3-ordered-points/
- // for details of below formula.
- ll val = (q.y - p.y) * (r.x - q.x) -
- (q.x - p.x) * (r.y - q.y);
- if (val == 0) return 0; // collinear
- return (val > 0)? 1: 2; // clock or counterclock wise
- }
- // The function that returns true if line segment 'p1q1'
- // and 'p2q2' intersect.
- bool doIntersect(point p1, point q1, point p2, point q2)
- {
- // Find the four orientations needed for general and
- // special cases
- int o1 = orientation(p1, q1, p2);
- int o2 = orientation(p1, q1, q2);
- int o3 = orientation(p2, q2, p1);
- int o4 = orientation(p2, q2, q1);
- // General case
- if (o1 != o2 && o3 != o4)
- return true;
- // Special Cases
- // p1, q1 and p2 are collinear and p2 lies on segment p1q1
- if (o1 == 0 && onSegment(p1, p2, q1)) return true;
- // p1, q1 and q2 are collinear and q2 lies on segment p1q1
- if (o2 == 0 && onSegment(p1, q2, q1)) return true;
- // p2, q2 and p1 are collinear and p1 lies on segment p2q2
- if (o3 == 0 && onSegment(p2, p1, q2)) return true;
- // p2, q2 and q1 are collinear and q1 lies on segment p2q2
- if (o4 == 0 && onSegment(p2, q1, q2)) return true;
- return false; // Doesn't fall in any of the above cases
- }
- bool intersect(segment laser,vector<segment> walls){
- //recieving the list of walls, and the laser beam segment
- for(int i=0;i<walls.size();i++){
- //checking the walls one by one
- if(doIntersect(laser.s,laser.e,walls[i].s,walls[i].e))
- return true;
- }
- return false;
- }
- void solve(){
- int t,n;
- vector<segment> walls;
- point pig, bird;
- segment laser,wall;
- cin>>t;
- while(t--){
- cin>>n;
- for(int i=0;i<n;i++){
- cin>>wall.s.x>>wall.s.y>>wall.e.x>>wall.e.y;
- walls.push_back(wall);
- }
- cin>>pig.x>>pig.y>>bird.x>>bird.y;
- laser.s = pig;
- laser.e = bird;
- if(intersect(laser,walls)){
- cout<<"Lose\n";
- }
- else{
- cout<<"Win\n";
- }
- walls.clear();
- }
- }
- int main() {
- Fin;
- Fout;
- FasterIO;
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement