API tools faq
paste
Advertisement
erfanul007

UVa 478

erfanul007
Apr 8th, 2021
475
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.39 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. // #include <iostream>
  3. // #include <cstdio>
  4. // #include <cstdlib>
  5. // #include <algorithm>
  6. // #include <cmath>
  7. // #include <vector>
  8. // #include <set>
  9. // #include <map>
  10. // #include <queue>
  11. // #include <stack>
  12. // #include <ctime>
  13. // #include <cassert>
  14. // #include <complex>
  15. // #include <string>
  16. // #include <cstring>
  17. // #include <bitset>
  18. using namespace std;
  19.  
  20. // #pragma GCC optimize("Ofast,no-stack-protector")
  21. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  22. // #pragma GCC optimize("unroll-loops")
  23.  
  24. #define ll              long long int
  25. #define vi              vector< int >
  26. #define vll             vector< ll >
  27.  
  28. #define sc              scanf
  29. #define pf              printf
  30. #define cspf(i)         pf("Case %d: ", i)
  31. #define spc             pf(" ")
  32. #define line            pf("\n")
  33.  
  34. #define ff              first
  35. #define ss              second
  36. #define mp              make_pair
  37. #define pb              push_back
  38. #define ppb             pop_back
  39. #define tp(v,j)         get<j>(v)
  40. #define Log(b,x)        (log(x)/log(b))
  41.  
  42. #define FOR(i,x,y)      for(int i = int(x); i < int(y); i++)
  43. #define ROF(i,x,y)      for(int i = int(x)-1; i >= int(y); i--)
  44. #define clr(arr,x)      memset(arr, x, sizeof arr)
  45. #define vout(v,sz)      for(int w=0;w<sz;w++){if(w) spc; cout<<v[w];}
  46. #define all(v)          v.begin(), v.end()
  47. #define rall(v)         v.rbegin(), v.rend()
  48. #define unq(v)          sort(all(v)),(v).resize(unique(all(v))-v.begin())
  49. #define fastIO          ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
  50.  
  51. #define sc1(x)          sc("%d",&x);
  52. #define sc2(x,y)        sc("%d %d", &x, &y)
  53. #define sc3(x,y,z)      sc("%d %d %d", &x, &y, &z)
  54. #define scl1(x)         sc("%lld",&x);
  55. #define scl2(x,y)       sc("%lld %lld", &x, &y)
  56. #define scf1(x)         sc("%lf",&x);
  57. #define scf2(x,y)       sc("%lf %lf", &x, &y)
  58.  
  59. #define pf1(x)          pf("%d",x);
  60. #define pf2(x,y)        pf("%d %d", x, y)
  61. #define pfl1(x)         pf("%lld",x);
  62. #define pfl2(x,y)       pf("%lld %lld", x, y)
  63.  
  64. #define MOD             (int)(998244353)
  65. #define MaxN            100000
  66. #define inf             0x3f3f3f3f
  67. #define PI              acos(-1.0)  // 3.1415926535897932
  68. #define eps             1e-9
  69.  
  70. #ifdef ERFANUL007
  71.     #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
  72.     template < typename Arg1 >
  73.     void __f(const char* name, Arg1&& arg1){
  74.         cout << name << " = " << arg1 << std::endl;
  75.     }
  76.     template < typename Arg1, typename... Args>
  77.     void __f(const char* names, Arg1&& arg1, Args&&... args){
  78.         const char* comma = strchr(names, ',');
  79.         cout.write(names, comma - names) << " = " << arg1 <<" | ";
  80.         __f(comma+1, args...);
  81.     }
  82. #else
  83.     #define debug(...)
  84. #endif
  85.  
  86. template <class T> inline T bigMod(T p,T e,T M){T ret=1; for(;e>0;e>>=1){ if(e&1) ret=(ret*p)%M; p=(p*p)%M;} return (T)ret;}
  87. template <class T> inline T modInverse(T a,T M){return bigMod(a,M-2,M);}
  88. template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
  89. template <class T> inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;}
  90.  
  91. int dx[] = { 1,-1, 0, 0};                //graph moves
  92. int dy[] = { 0, 0, 1,-1};               //graph moves
  93.  
  94. struct PT{
  95.     double x, y;
  96.     void scan(){ scanf("%lf %lf",&x,&y);}
  97. };
  98.  
  99.  
  100. double SQ(double x){ return x*x;}
  101.  
  102. double Dis(PT a,PT b){ return SQ(a.x - b.x) + SQ(a.y - b.y);}
  103.  
  104. double absDis(PT a,PT b){ return sqrt(Dis(a,b));}
  105.  
  106. /*two vector lines Dot product*/
  107. int Dot(PT a,PT b){ return a.x*b.x + a.y*b.y;}
  108.  
  109. /*two vector lines Cross product*/
  110. int Cross(PT a,PT b){ return a.x*b.y - b.x*a.y;}
  111.  
  112. /*convert degree to radian*/
  113. double toRadian(double x){ return (x*(PI/180.0));}
  114.  
  115. /*convert radian to degree*/
  116. double toDegree(double x){ return (x*(180.0/PI));}
  117.  
  118. /*two point's vector line*/
  119. PT vect(PT a,PT b){ return {a.x-b.x, a.y-b.y};}
  120.  
  121. /*convert a coordinate p from cartesian to polar
  122. r = sqrt(x*x + y*y)
  123. theta = atan(y/x) [in radian]*/
  124. PT toPolar(PT p){
  125.     return {sqrt(SQ(p.x)+SQ(p.y)), atan(p.y/p.x)};
  126. }
  127.  
  128. /*convert a coordinate p from polar to cartesian
  129. theta must be radian
  130. x = r * cos(theta)
  131. y = r * sin(theta)*/
  132. PT toCartesian(PT a){
  133.     return {a.x * cos(a.y), a.x * sin(a.y)};
  134. }
  135.  
  136. /*divide line ab into m:n and return midpoint*/
  137. /*For 3D add the z part same as x and y*/
  138. PT divideLine(PT a, PT b, double m, double n){
  139.     return {(a.x * m + b.x * n)/(m+n),
  140.         (a.y * m + b.y * n)/(m+n)};
  141. }
  142.  
  143. /*line ab to point c
  144. 0 => if ab and c coliner
  145. + => clockwise
  146. - => anticlockwise
  147. */
  148. int orientation(PT a, PT b, PT c)
  149. {
  150.     double val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
  151.     if(abs(val) < eps) return 0;
  152.     if(val > eps) return 1;
  153.     return -1;
  154. }
  155.  
  156. struct Rectangle
  157. {
  158.     int fig;
  159.     PT A, B, C, D;
  160.     void scan(int _fig){
  161.         A.scan();
  162.         C.scan();
  163.         B = {C.x, A.y};
  164.         D = {A.x, C.y};
  165.         fig = _fig;
  166.     }
  167.     bool inside(PT P){
  168.         int val1 = orientation(A, B, P);
  169.         int val2 = orientation(B, C, P);
  170.         int val3 = orientation(C, D, P);
  171.         int val4 = orientation(D, A, P);
  172.         if(val1 == val2 && val2 == val3 && val3 == val4) return true;
  173.         return false;
  174.     }
  175. };
  176.  
  177. struct Circle
  178. {
  179.     int fig;
  180.     PT A;
  181.     double r;
  182.     void scan(int _fig){
  183.         A.scan();
  184.         scanf("%lf", &r);
  185.         fig = _fig;
  186.     }
  187.     bool inside(PT P){
  188.         double dis = absDis(A, P);
  189.         if(dis + eps < r) return true;
  190.         return false;
  191.     }
  192. };
  193.  
  194. struct Triangle
  195. {
  196.     int fig;
  197.     PT A, B, C;
  198.     void scan(int _fig){
  199.         A.scan();
  200.         B.scan();
  201.         C.scan();
  202.         fig = _fig;
  203.     }
  204.     bool inside(PT P){
  205.         int val1 = orientation(A, B, P);
  206.         int val2 = orientation(B, C, P);
  207.         int val3 = orientation(C, A, P);
  208.         if(val1 == val2 && val2 == val3) return true;
  209.         return false;
  210.     }
  211. };
  212.  
  213. /*line ab and line cd is parrallel if ab X cd = 0 */
  214. bool ifParallel(PT a,PT b,PT c,PT d)
  215. {
  216.     if(Cross(vect(a,b),vect(c,d)) != 0) // for double abs(val) > eps
  217.         return false;
  218.     return true;
  219. }
  220.  
  221. /*line ab and line cd is perpendicular if ab . cd = 0 */
  222. bool ifPerpendicular(PT a,PT b,PT c,PT d)
  223. {
  224.     if(Dot(vect(a,b),vect(c,d)) != 0) // for double abs(val) > eps
  225.         return false;
  226.     return true;
  227. }
  228.  
  229. /*Area*/
  230.  
  231. double heronTriangle(double a, double b, double c){
  232.     double s = (a + b + c) / 2.0;
  233.     if(s - a < 0) return -1;
  234.     if(s - b < 0) return -1;
  235.     if(s - c < 0) return -1;
  236.     return sqrt(s * (s - a) * (s - b) * (s - c));
  237. }
  238.  
  239. double mdedianTriangle(double a, double b, double c){
  240.     double s = (a + b + c) / 2.0;
  241.     if(s - a < 0) return -1;
  242.     if(s - b < 0) return -1;
  243.     if(s - c < 0) return -1;
  244.     return (4.0 / 3.0 ) * sqrt(s * (s - a) * (s - b) * (s - c));
  245. }
  246.  
  247. double trapeziumArea(double a, double b, double h){
  248.     return (a + b) * h / 2.0;
  249. }
  250.  
  251. ///Area of irregular polygon
  252. double AreaOfPolygon(int n,PT a[])
  253. {
  254.     double area = 0.0;
  255.     for(int i=1;i<n;i++){
  256.         area+=(a[i-1].x*a[i].y-a[i].x*a[i-1].y);
  257.     }
  258.     area+=(a[n-1].x*a[0].y-a[0].x*a[n-1].y);
  259.     return area/2.0;
  260. }
  261.  
  262. /*volumn*/
  263.  
  264. double coneVolume(double r, double h){
  265.     return PI * r * r * h / 3.0;
  266. }
  267.  
  268. double CircumcircleR(double a, double b, double c){
  269.     if(a + b + c < eps) return 0;
  270.     return (a * b * c) / sqrt((a + b + c) * (b + c - a) * (c + a - b) * (a + b - c));
  271. }
  272.  
  273. double IncircleR(double a, double b, double c){
  274.     if(a + b + c < eps) return 0;
  275.     return 2.0 * heronTriangle(a, b, c) / (a + b + c);
  276. }
  277.  
  278. bool insideRectangle(PT p, PT a, PT c){
  279.     if(p.x < a.x or p.x > c.x) return false;
  280.     if(p.y < a.y or p.y > c.y) return false;
  281.     return true;
  282. }
  283.  
  284. /*checking shapes*/
  285.  
  286. bool isSquare(PT *a){
  287.     if(abs(Dis(a[0], a[1]) - Dis(a[1], a[2])) > eps
  288.         or abs(Dis(a[1], a[2]) - Dis(a[2], a[3])) > eps
  289.         or abs(Dis(a[2], a[3]) - Dis(a[3], a[0])) > eps)
  290.         return false;
  291.     if(!ifPerpendicular(a[0], a[1], a[1], a[2])) return false;
  292.     return true;
  293. }
  294.  
  295. bool isRectangle(PT *a){
  296.     if(abs(Dis(a[0], a[1]) - Dis(a[3], a[2])) > eps
  297.         or abs(Dis(a[1], a[2]) - Dis(a[0], a[3])) > eps)
  298.         return false;
  299.     if(!ifPerpendicular(a[0], a[1], a[1], a[2])) return false;
  300.     return true;
  301. }
  302.  
  303. bool isRombus(PT *a){
  304.     if(abs(Dis(a[0], a[1]) - Dis(a[1], a[2])) > eps
  305.         or abs(Dis(a[1], a[2]) - Dis(a[2], a[3])) > eps
  306.         or abs(Dis(a[2], a[3]) - Dis(a[3], a[0])) > eps)
  307.         return false;
  308.     return true;
  309. }
  310.  
  311. bool isParallelogram(PT *a){
  312.     if(abs(Dis(a[0], a[1]) - Dis(a[3], a[2])) > eps
  313.         or abs(Dis(a[1], a[2]) - Dis(a[0], a[3])) > eps)
  314.         return false;
  315.     return true;
  316. }
  317.  
  318. bool isTrapezium(PT *a){
  319.     if(!ifParallel(a[0], a[1], a[3], a[2])
  320.         and !ifParallel(a[1], a[2], a[0], a[3])) return false;
  321.     return true;
  322. }
  323.  
  324.  
  325. PT f; //init first coordinate
  326. //for clockwise sorting
  327. bool ClockCmp(PT &a,PT &b){ return (f.x-a.x)*(f.y-b.y)<(f.x-b.x)*(f.y-a.y);}
  328.  
  329. //for anti-clockwise sorting
  330. bool AClockCmp(PT &a,PT &b){ return (f.x-a.x)*(f.y-b.y)>(f.x-b.x)*(f.y-a.y);}
  331.  
  332. int main()
  333. {
  334.     #ifndef ONLINE_JUDGE
  335.         clock_t tStart = clock();
  336.         freopen("input.txt", "r", stdin);
  337.         freopen("output.txt", "w", stdout);
  338.     #endif
  339.  
  340.     vector<Rectangle>RR;
  341.     vector<Circle>CC;
  342.     vector<Triangle>TT;
  343.  
  344.     int fig=0;
  345.     char c;
  346.     while(scanf("%c", &c)!=EOF){
  347.         if(c=='*') break;
  348.         fig++;
  349.         // debug(c, fig);
  350.         if(c == 'r'){
  351.             Rectangle X;
  352.             X.scan(fig);
  353.             RR.pb(X);
  354.         }
  355.         else if(c == 'c'){
  356.             Circle X;
  357.             X.scan(fig);
  358.             CC.pb(X);
  359.         }
  360.         else if(c == 't'){
  361.             Triangle X;
  362.             X.scan(fig);
  363.             TT.pb(X);
  364.         }
  365.         getchar();
  366.     }
  367.     // debug(RR.size(), CC.size(), TT.size());
  368.  
  369.     double x, y;
  370.     int point = 0;
  371.  
  372.     while(scanf("%lf %lf", &x, &y)!=EOF){
  373.         if(abs(x-9999.9)<eps && abs(y-9999.9)<eps) break;
  374.         point++;
  375.         PT P = {x, y};
  376.         vector< int > ans;
  377.         for(auto rec : RR){
  378.             if(rec.inside(P)){
  379.                 ans.pb(rec.fig);
  380.             }
  381.         }
  382.         for(auto rec : CC){
  383.             if(rec.inside(P)){
  384.                 ans.pb(rec.fig);
  385.             }
  386.         }
  387.         for(auto rec : TT){
  388.             if(rec.inside(P)){
  389.                 ans.pb(rec.fig);
  390.             }
  391.         }
  392.         if(ans.size()){
  393.             sort(all(ans));
  394.             for(auto num : ans){
  395.                 pf("Point %d is contained in figure %d\n", point, num);
  396.             }
  397.         }
  398.         else pf("Point %d is not contained in any figure\n", point);
  399.     }
  400.  
  401.     #ifndef ONLINE_JUDGE
  402.         fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
  403.     #endif
  404.  
  405.     return 0;
  406. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!