fork(2) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #define EPS 0.000001
  6. using namespace std;
  7.  
  8. class owad
  9. {
  10. 	int ilosc_kolizji;
  11. 	float xs, xf, yf, a, b;
  12. 	bool dopuszczona, punkt_prosta_pionowa;
  13. 	void interpoluj();
  14.  
  15. public:
  16. 	owad();
  17. 	owad(int xs, int xf, int yf);
  18. 	void PunktyWspolne(owad &bied);
  19. 	bool CzyDopuszczona() { return dopuszczona; }
  20. 	bool CzyKolizje() { if (ilosc_kolizji > 0) return true; else return false; }
  21. 	void ZerujKolizje() { ilosc_kolizji = 0; }
  22. 	void Zabron() { dopuszczona = false; ilosc_kolizji = 0;  /*cout << "bronie" << endl;*/ }
  23.  
  24. 	bool operator < (const owad& bied) const
  25. 	{
  26. 		//cout << "sortuje" << endl;
  27. 		return (ilosc_kolizji < bied.ilosc_kolizji);
  28. 	}
  29.  
  30. };
  31.  
  32.  
  33.  
  34. int main()
  35. {
  36. 	int ilosc, xs, xf, yf, ilosc_dopuszczonych, licz = 0;
  37. 	vector <owad> biedronka;
  38.  
  39. 	cin >> ilosc;
  40. 	biedronka.reserve(ilosc);
  41. 	for (int i = 0; i < ilosc; ++i)
  42. 	{
  43. 		cin >> xs >> xf >> yf;
  44. 		biedronka.push_back(owad(xs, xf, yf));
  45. 	}
  46. 	///////////////////////////////////////////////////////////////////
  47.  
  48. 	do
  49. 	{
  50. 		for (int i = 0; i < ilosc; ++i)
  51. 		{
  52. 			biedronka[i].ZerujKolizje();
  53. 		}
  54. 		for (int i = 0; i < ilosc; ++i)
  55. 		{
  56. 			for (int j = i; j < ilosc; ++j)
  57. 			{
  58. 				if ((i != j) && (biedronka[i].CzyDopuszczona()) && (biedronka[j].CzyDopuszczona()))
  59. 				{
  60. 					biedronka[i].PunktyWspolne(biedronka[j]);
  61. 					//cout << "szukam punktow wspolnych " << i << "z " << j << endl;
  62. 				}
  63. 			}
  64. 		}
  65.  
  66. 		sort(biedronka.begin(), biedronka.end());   //trasa o najwiekszej ilosci kolizji na koniec wektora
  67. 		/*for (int i = 0; i < ilosc; ++i)
  68. 		{
  69. 			cout << biedronka[i].ilosc_kolizji << endl;
  70. 		}*/
  71. 		if (biedronka[ilosc-1].CzyKolizje())
  72. 		{
  73. 			biedronka[ilosc-1].Zabron();
  74. 			//cout << "wykryto kolizje" << endl;
  75. 		}
  76. 		//cout << licz << endl;
  77. 		//++licz;
  78. 		sort(biedronka.begin(), biedronka.end());
  79. 	} while (biedronka[ilosc-1].CzyKolizje());
  80. 	ilosc_dopuszczonych = 0;
  81. 	//cout << endl << ilosc_dopuszczonych << endl;
  82. 	for (int i = 0; i < ilosc; ++i)
  83. 	{
  84. 		if (biedronka[i].CzyDopuszczona())
  85. 		{
  86. 			++ilosc_dopuszczonych;
  87. 		}
  88. 	}
  89. 	cout << ilosc_dopuszczonych << endl;
  90. 	//system("pause");
  91. 	return 0;
  92. }
  93.  
  94. void owad::interpoluj()
  95. {
  96. 	if (fabs(xs - xf) < EPS)
  97. 	{
  98. 		punkt_prosta_pionowa = true;
  99.  
  100. 	}
  101. 	else
  102. 	{
  103. 		a = -yf / (xs - xf);
  104. 		b = (xs*yf) / (xs - xf);
  105. 		//cout << a << endl << b << endl;
  106. 	}
  107.  
  108. }
  109.  
  110. owad::owad(int xs, int xf, int yf) : dopuszczona(true), punkt_prosta_pionowa(false), xs(xs), xf(xf), yf(yf), ilosc_kolizji(0)
  111. {
  112. 	interpoluj();
  113. }
  114.  
  115. void owad::PunktyWspolne(owad &bied)
  116. {
  117. 	float wspolny_x, wspolny_y;
  118.  
  119. 	if ((punkt_prosta_pionowa) && (bied.punkt_prosta_pionowa))
  120. 	{
  121. 		if (fabs(xs - bied.xs) < EPS)
  122. 		{
  123. 			++ilosc_kolizji;
  124. 			++bied.ilosc_kolizji;
  125. 			//cout << "tu jest kolizja" << endl;
  126. 		}
  127. 	} else
  128. 	if ((punkt_prosta_pionowa) && !(bied.punkt_prosta_pionowa))
  129. 	{
  130. 		//cout << (xs * bied.a + bied.b) << endl;
  131. 		if (((((xs * bied.a + bied.b) < yf) || (fabs((xs * bied.a + bied.b) - yf) < EPS)) && (((xs * bied.a + bied.b) > 0)||(fabs(xs * bied.a + bied.b)<EPS))) && (((bied.xs < xs) || (fabs(bied.xs - xs) < EPS)) && ((bied.xf > xs) || (fabs(bied.xf - xs) < EPS)) || (((bied.xs > xs) || (fabs(bied.xs - xs) < EPS)) && ((bied.xf < xs) || (fabs(bied.xf - xs) < EPS)))))
  132. 		{
  133. 			{
  134. 				++ilosc_kolizji;
  135. 				++bied.ilosc_kolizji;
  136. 			}
  137. 		}
  138. 	} else
  139.  
  140. 	if ((bied.punkt_prosta_pionowa) && !(punkt_prosta_pionowa))
  141. 	{
  142. 		if (((((bied.xs * a + b) < bied.yf) || (fabs((bied.xs * a + b) - bied.yf) < EPS)) && (((bied.xs * a + b) > 0)||(fabs(bied.xs * a + b)<EPS))) && (((xs < bied.xs) || (fabs(xs - bied.xs) < EPS)) && ((xf > bied.xs) || (fabs(xf - bied.xs) < EPS)) || (((xs > bied.xs) || (fabs(xs-bied.xs) < EPS)) && ((xf < bied.xs) || (fabs(xf-bied.xs) < EPS)))))
  143. 		{
  144. 			{
  145. 				++ilosc_kolizji;
  146. 				++bied.ilosc_kolizji;
  147. 			}
  148. 			//cout << "kolizja" << endl;
  149. 		}
  150. 	}
  151. 	else
  152. 		if (!(punkt_prosta_pionowa) && !(bied.punkt_prosta_pionowa))
  153. 		{
  154. 			//cout << "dzialam" << endl;
  155. 			//cout << bied.a << endl << a << endl;
  156. 			if (fabs(bied.a - a) > EPS)
  157. 			{
  158. 				wspolny_x = (b - bied.b) / (bied.a - a);
  159. 				wspolny_y = (bied.a * b - a * bied.b) / (bied.a - a);
  160. 				//cout << wspolny_x << endl << wspolny_y << endl;
  161. 				if (((((wspolny_x > xs) || (fabs(wspolny_x - xs) < EPS)) && ((wspolny_x < xf) || (fabs(wspolny_x - xf) < EPS))) || (((wspolny_x < xs) || (fabs(wspolny_x - xs) < EPS)) && ((wspolny_x > xf) || (fabs(wspolny_x - xf) < EPS)))) && (((wspolny_y > 0) || (fabs(wspolny_y<EPS))) && ((wspolny_y < yf) || (fabs(wspolny_y - yf) < EPS ))))
  162. 				{
  163. 					//if ((((wspolny_x >= bied.xs) && (wspolny_x <= bied.xf)) || ((wspolny_x <= bied.xs) && (wspolny_x >= bied.xf))) && ((wspolny_y > 0) && (wspolny_y <= bied.yf)))
  164. 					if (((((wspolny_x > bied.xs) || (fabs(wspolny_x - bied.xs) < EPS)) && ((wspolny_x < bied.xf) || (fabs(wspolny_x - bied.xf) < EPS))) || (((wspolny_x < bied.xs) || (fabs(wspolny_x - bied.xs) < EPS)) && ((wspolny_x > bied.xf) || (fabs(wspolny_x - bied.xf) < EPS)))) && (((wspolny_y > 0)||(fabs(wspolny_y<EPS))) && ((wspolny_y < bied.yf) || (fabs(wspolny_y - bied.yf) < EPS))))
  165. 					{
  166. 						//cout << "dzialam" << endl;
  167. 						++ilosc_kolizji;
  168. 						++bied.ilosc_kolizji;
  169. 					}
  170. 				}
  171. 			}
  172. 			else
  173. 			{
  174. 				if ((fabs(a - bied.a) < EPS) && (fabs(b - bied.b) < EPS))
  175. 				{
  176. 					{
  177. 						++ilosc_kolizji;
  178. 						++bied.ilosc_kolizji;
  179. 					} 
  180. 				}
  181. 			}
  182. 		}
  183. }
Success #stdin #stdout 0s 3424KB
comments (?)
stdin 
3
0 0 10
-10 0 10
10 0 10
stdout 
1
https://ideone.com/KEPqEd
problem ETI06E3, based on SPOJ submission 16202973 (C++ 5), 2016-01-31 15:28:29
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!