Advertisement
hkshakib

Untitled

Feb 20th, 2020
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.09 KB | None | 0 0
  1. #include<bits /stdc++.h>
  2. using namespace std ;
  3. struct point {
  4. int x, y ;
  5. point () {}
  6. point ( int a, int b) {
  7. x=a, y=b;
  8. }
  9. };
  10. int trun ( point p0, point p1, point p2) {
  11. int result=(p2 .x−p0 . x)*(p1 .y−p0 . y)−(p1 .x−p0 . x)*(p2 .y−p0 . y) ;
  12. if ( result >0)
  13. return 1;
  14. if ( result < 0)
  15. return −1;
  16. return result ;
  17. }
  18. bool on segment ( point pi, point pj, point pk) {
  19. int minx=min( pi .x, pj . x) ;
  20. int maxx=max( pi .x, pj . x) ;
  21. int miny=min( pi .y, pj . y) ;
  22. int maxy=max( pi .y, pj . y) ;
  23. if (pk .x>=minx&&pk .x<=maxx&&pk .y>=miny&&pk .y<=maxy)
  24. return true ;
  25. return false ;
  26. }
  27. bool Segment intersect ( point p1, point p2, point p3, point p4) {
  28. int d1=trun (p3, p4, p1) ;
  29. int d2=trun (p3, p4, p2) ;
  30. int d3=trun (p1, p2, p3) ;
  31. int d4=trun (p1, p2, p4) ;
  32. if ((d1*d2<0)&&(d3*d4<0))
  33. return true ;
  34. if (d1==0&&on segment (p3, p4, p1) )
  35. return true ;
  36. if (d2==0&&on segment (p3, p4, p2) )
  37. return true ;
  38. if (d3==0&&on segment (p1, p2, p3) )
  39. return true ;
  40. if (d4==0&&on segment (p1, p2, p4) )
  41. return true ;
  42. return false ;
  43.  
  44. }
  45. bool in poligon ( vector<point>p, point given, point inf2 ) {
  46. int intersect =0;
  47. int N=p. size () ;
  48. for ( int i =0; i<N; i++) {
  49. point p1=p[ i ] ;
  50. point p2=p [( i+1)%N] ;
  51. if ( Segment intersect (p1, p2, given, inf2 ) ) {
  52. intersect++;
  53. }
  54. }
  55. return intersect%2==1;
  56. }
  57. int main() {
  58. int N;
  59. while ( scanf (”%d”,&N)&&N) {
  60. int Max=−10005;
  61. vector<point>poligon ;
  62. for ( int i =0; i<N; i++) {
  63. int x, y ;
  64. scanf (”%d %d”,&x,&y) ;
  65. poligon . push back ( point (x, y) ) ;
  66. Max=max(x,Max) ;
  67. }
  68. int x, y ;
  69. scanf (”%d %d”,&x,&y) ;
  70. if ( in poligon ( poligon, point (x, y), point (Max, y) ) ) {
  71. printf (”T\n”) ;
  72. } else {
  73. printf (”F\n”) ;
  74. }
  75. }
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement