API tools faq
paste
View difference between Paste ID: R75WdpR3 and nYxwJzwV
SHOW: | | - or go back to the newest paste.
1
#include <iostream>
2
#include <cstdio>
3
#include <cmath>
4
#include <algorithm>
5
#include <vector>
6
7
using namespace std;

8
9
bool isEq(double a, double b)

10
{

11
	return (abs(a - b) < 1e-9);

12
}

13
14
struct point {

15
	double x, y;

16-
	bool operator==(point& p)

16+
	bool operator==(const point& p)const

17
	{

18
		return (isEq(x, p.x) && isEq(y, p.y));

19
	}

20
};

21
22
struct segment {

23
	point st, en;

24
	segment() { st = {0, 0}; en = {0, 0}; }

25
	segment(point A, point B) { st = A; en = B; }

26-
	bool operator==(segment& AB)

26+
	bool operator==(const segment& AB)const

27
	{

28-
		return ((st == AB.st && en == AB.en) || (en == AB.st && st == AB.en));

28+
		return ((st == AB.st && en == AB.en) || (st == AB.en && en == AB.st));

29
	}

30
};

31
32
double det(point& a, point& b, point& c)

33
{

34-
	return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.y*(a.y - b.y);

34+
	return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y);

35
}

36
37-
bool isIntersect(segment& AB, segment& CD)

37+
bool isIntersect(segment& AB, segment& CD, point& p)

38
{

39-
	int ABC = det(AB.st, AB.en, CD.st);

39+
	double ABC = det(AB.st, AB.en, CD.st);

40-
	int ABD = det(AB.st, AB.en, CD.en);

40+
	double ABD = det(AB.st, AB.en, CD.en);

41-
	int CDA = det(CD.st, CD.en, AB.st);

41+
	double CDA = det(CD.st, CD.en, AB.st);

42-
	int CDB = det(CD.st, CD.en, AB.en);

42+
	double CDB = det(CD.st, CD.en, AB.en);

43-
	if (((ABC > 0 && ABD < 0) || (ABC < 0 && ABD > 0)) && ((CDA > 0 && CDB < 0) || (CDA < 0 && CDB > 0)))return 1;

43+
44-
	else {

44+
	if (((ABC > 0 && ABD < 0) || (ABC < 0 && ABD > 0)) && ((CDA > 0 && CDB < 0) || (CDA < 0 && CDB > 0))) {

45-
		if (isEq(ABC, 0))return (max(AB.st.x, AB.en.x) >= CD.st.x && min(AB.st.x, AB.en.x) <= CD.st.x) && (max(AB.st.y, AB.en.y) >= CD.st.y && min(AB.st.y, AB.en.y) <= CD.st.y);

45+
		if (isEq(AB.st.x, AB.en.x)) {

46-
		if (isEq(ABD, 0))return (max(AB.st.x, AB.en.x) >= CD.en.x && min(AB.st.x, AB.en.x) <= CD.en.x) && (max(AB.st.y, AB.en.y) >= CD.en.y && min(AB.st.y, AB.en.y) <= CD.en.y);

46+
			p.x = AB.st.x;

47
			p.y = ((CD.st.y - CD.en.y) / (CD.st.x - CD.en.x))*(p.x - CD.st.x) + CD.st.y;

48-
		if (isEq(CDA, 0))return (max(CD.st.x, CD.en.x) >= AB.st.x && min(CD.st.x, CD.en.x) <= AB.st.x) && (max(CD.st.y, CD.en.y) >= AB.st.y && min(CD.st.y, CD.en.y) <= AB.st.y);

48+
			return 1;

49-
		if (isEq(CDB, 0))return (max(CD.st.x, CD.en.x) >= AB.en.x && min(CD.st.x, CD.en.x) <= AB.en.x) && (max(CD.st.y, CD.en.y) >= AB.en.y && min(CD.st.y, CD.en.y) <= AB.en.y);

49+
50
		if (isEq(CD.st.x, CD.en.x)) {

51
			p.x = CD.st.x;

52
			p.y = ((AB.st.y - AB.en.y) / (AB.st.x - AB.en.x))*(p.x - AB.st.x) + AB.st.y;

53-
void intersectionPoint(segment AB, segment CD, point &p)

53+
			return 1;

54
		}

55-
	if (isEq(AB.st.x, AB.en.x)) {

55+
56-
		p.x = AB.st.x;

56+
		double a1, b1, c1, a2, b2, c2;

57-
		p.y = ((CD.st.y - CD.en.y) / (CD.st.x - CD.en.x))*(p.x - CD.st.x);

57+
		a1 = AB.st.y - AB.en.y;

58-
		return;

58+
		b1 = AB.en.x - AB.st.x;

59
		c1 = (AB.st.y*b1 + AB.st.x*a1);

60-
	if (isEq(CD.st.x, CD.en.x)) {

60+
61-
		p.x = CD.st.x;

61+
		a2 = CD.st.y - CD.en.y;

62-
		p.y = ((AB.st.y - AB.en.y) / (AB.st.x - AB.en.x))*(p.x - AB.st.x);

62+
		b2 = CD.en.x - CD.st.x;

63-
		return;

63+
		c2 = (CD.st.y*b2 + CD.st.x*a2);

64
65
		p.x = (b2*c1 - b1*c2) / (b2*a1 - b1*a2);

66-
	double a1, b1, c1, a2, b2, c2;

66+
		p.y = (c1 - a1*p.x) / b1;

67-
	a1 = AB.st.y - AB.en.y;

67+
		return 1;

68-
	b1 = AB.en.x - AB.st.x;

68+
69-
	c1 = (AB.st.y*b1 + AB.st.x*a1);

69+
	else if (isEq(ABC, 0)) {

70
		if ((max(AB.st.x, AB.en.x) > CD.st.x && min(AB.st.x, AB.en.x) < CD.st.x) && (max(AB.st.y, AB.en.y) > CD.st.y && min(AB.st.y, AB.en.y) < CD.st.y)) {

71-
	a2 = CD.st.y - CD.en.y;

71+
			p = CD.st;

72-
	b2 = CD.en.x - CD.st.x;

72+
			return 1;

73-
	c2 = (CD.st.y*b2 + CD.st.x*a2);

73+
74
	}

75-
	p.x = (b2*c1 - b1*c2) / (b2*a1 - b1*a2);

75+
	else if (isEq(ABD, 0)) {

76-
	p.y = (c1 - a1*p.x) / b1;

76+
		if ((max(AB.st.x, AB.en.x) > CD.en.x && min(AB.st.x, AB.en.x) < CD.en.x) && (max(AB.st.y, AB.en.y) > CD.en.y && min(AB.st.y, AB.en.y) < CD.en.y)) {

77-
	return;

77+
			p = CD.en;

78
			return 1;

79
		}

80
	}

81
82
	else if (isEq(CDA, 0)) {

83
		if ((max(CD.st.x, CD.en.x) > AB.st.x && min(CD.st.x, CD.en.x) < AB.st.x) && (max(CD.st.y, CD.en.y) > AB.st.y && min(CD.st.y, CD.en.y) < AB.st.y)) {

84
			p = AB.st;

85
			return 1;

86
		}

87
	}

88
	else if (isEq(CDB, 0)) {

89
		if ((max(CD.st.x, CD.en.x) > AB.en.x && min(CD.st.x, CD.en.x) < AB.en.x) && (max(CD.st.y, CD.en.y) > AB.en.y && min(CD.st.y, CD.en.y) < AB.en.y)) {

90
			p = CD.en;

91
			return 1;

92
		}

93
	}

94
	else return 0;

95
}

96
97
int main()

98
{

99-
					if (isIntersect(lines[i], lines[j])){

99+
	//freopen("out.txt", "w", stdout);

100
	int i, j, k, l, t, n;

101-
						point p;

101+
102-
						intersectionPoint(lines[i], lines[j], p);

102+
103
		scanf("%d", &n);

104
		vector<segment>lines;

105
		segment AB;

106
		for (i = 0; i < n; i++) {

107
			scanf("%lf %lf %lf %lf", &AB.st.x, &AB.st.y, &AB.en.x, &AB.en.y);

108
			lines.push_back(AB);

109
		}

110
111
		vector<segment>lines2, lines3;

112
		//cout << lines[1] == lines[1] << endl;

113
		bool f = false;

114
		point p;

115-
				lines.erase(find(lines.begin(), lines.end(), lines3[i]));

115+
116
			int s = lines.size();

117
			f = false;

118
			for (i = 0; i < s; i++) {

119
				for (j = i + 1; j < s; j++) {

120
					if (isIntersect(lines[i], lines[j], p)){

121
						f = true;

122
						cout << lines[i].st.x << ','<< lines[i].st.y << "  " << lines[i].en.x << ',' << lines[i].en.y << '\t' << lines[j].st.x << ',' << lines[j].st.y << "  " << lines[j].en.x << ',' << lines[j].en.y << '\t' << p.x << ',' << p.y << endl;

123-
			if (count(lines2.begin(), lines2.end(), lines[i]) == 0)lines2.push_back(lines[i]);

123+
124
						lines2.push_back(segment(p, lines[i].en));

125
						lines2.push_back(segment(p, lines[j].st));

126
						lines2.push_back(segment(p, lines[j].en));

127
						

128
						lines3.push_back(lines[i]);

129
						lines3.push_back(lines[j]);

130
					}

131
				}

132
			}

133
134
			vector<segment>::iterator it;

135
			for (i = 0; i < lines3.size(); i++) {

136
				it = find(lines.begin(), lines.end(), lines3[i]);

137
				if(it != lines.end())lines.erase(it);

138
			}

139
			lines.reserve(lines.size() + lines2.size());

140
			lines.insert(lines.end(), lines2.begin(), lines2.end());

141
142
			lines2.clear();

143
			lines3.clear();

144
		} while (f);

145
146
		lines2.clear();

147
		for (i = 0; i < lines.size(); i++) {

148
			if (count(lines2.begin(), lines2.end(), lines[i]) == 0) {

149
				lines2.push_back(lines[i]);

150
				cout << lines[i].st.x << ' ' << lines[i].st.y << '\t' << lines[i].en.x << ' ' << lines[i].en.y << endl;

151
			}

152
		}

153
		printf("%d\n", lines2.size());

154
	}

155
	return 0;

156
}
        

    


            


                                


        

            



                
    

        Public Pastes
    

    
            

    

                    

        

    





    


    
    
    
    
    
    
    
    




    


    



                

            We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.             OK, I Understand
        

    
                

            

                
                    
                
            

            

                Not a member of Pastebin yet?

                Sign Up, it unlocks many cool features!