-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path335_Self_Crossing.cpp
114 lines (114 loc) · 3.14 KB
/
335_Self_Crossing.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<iostream>
#include<vector>
using namespace std;
struct Line
{
int x1;
int y1;
int x2;
int y2;
Line(int a, int b, int c, int d) :x1(a), y1(b), x2(c), y2(d){}
};
class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
if (x.size() < 4)
return false;
Line *rightLine = new Line(0, 0, 0, x.at(0));
Line *upLine = new Line(-x.at(1), x.at(0), 0, x.at(0));
Line *leftLine = new Line(-x.at(1), x.at(0) - x.at(2), -x.at(1), x.at(0));
Line *downLine = new Line(-x.at(1), x.at(0) - x.at(2), -x.at(1) + x.at(3), x.at(0) - x.at(2));
if (x.at(2) <= x.at(0) && x.at(3) >= x.at(1))
return true;
int curX = x.at(3) - x.at(1), curY = x.at(0) - x.at(2), i = 4;
while (i < x.size())
{
if (i % 4 == 0)//up
{
if (curX == rightLine->x1&&curY + x.at(i) >= rightLine->y1&&curY + x.at(i) <= rightLine->y2)//cross with rightLine
return true;
if (curX >= upLine->x1&&curX <= upLine->x2&&curY + x.at(i) >= upLine->y1)//cross with upLine
return true;
if (curX > rightLine->x1 && curY + x.at(i) >= rightLine->y1&&curY+x.at(i)<=rightLine->y2)
{
Line* temp = leftLine;
leftLine = rightLine;
rightLine = temp;
}
rightLine->x1 = curX;
rightLine->y1 = curY;
curY += x.at(i);
rightLine->x2 = curX;
rightLine->y2 = curY;
}
if (i % 4 == 1)//left
{
if (curY == upLine->y1&&curX - x.at(i) >= upLine->x1&&curX - x.at(i) <= upLine->x2)
return true;
if (curY >= leftLine->y1&&curY <= leftLine->y2&&curX - x.at(i) <= leftLine->x1)
return true;
if (curY > upLine->y1 && curX-x.at(i)>=upLine->x1&&curX-x.at(i)<=upLine->x2)
{
Line* temp = downLine;
downLine = upLine;
upLine = temp;
}
upLine->x1 = curX - x.at(i);
upLine->y1 = curY;
upLine->x2 = curX;
upLine->y2 = curY;
curX -= x.at(i);
}
if (i % 4 == 2)//down
{
if (curX == leftLine->x1&&curY - x.at(i) >= leftLine->y1&&curY - x.at(i) <= leftLine->y2)
return true;
if (curX >= downLine->x1&&curX <= downLine->x2&&curY - x.at(i) <= downLine->y1)
return true;
if (curX < leftLine->x1&&curY - x.at(i) >= leftLine->y1&&curY - x.at(i) <= leftLine->y2)
{
Line* temp = rightLine;
rightLine = leftLine;
leftLine = temp;
}
leftLine->x1 = curX;
leftLine->y1 = curY - x.at(i);
leftLine->x2 = curX;
leftLine->y2 = curY;
curY -= x.at(i);
}
if (i % 4 == 3)//right
{
if (curY == downLine->y1&&curX + x.at(i) >= downLine->x1&&curX + x.at(i) <= downLine->x2)//cross with downLine
return true;
if (curY >= rightLine->y1&&curY <= rightLine->y2&&curX + x.at(i) >= rightLine->x1)
return true;
if (curY < downLine->y1&&curX + x.at(i) >= downLine->x1&&curX + x.at(i) <= downLine->x2)
{
Line* temp = upLine;
upLine = downLine;
downLine = temp;
}
downLine->x1 = curX;
downLine->y1 = curY;
curX += x.at(i);
downLine->x2 = curX;
downLine->y2 = curY;
}
i++;
}
return false;
}
};
int main()
{
Solution s;
vector<int> test;
test.push_back(1);
test.push_back(2);
test.push_back(3);
test.push_back(4);
test.push_back(2);
test.push_back(3);
cout << s.isSelfCrossing(test) << endl;
}