fork download 
  1. /*
  2.   Zenit CK 2011/2012, uloha f)
  3.  
  4.   Dany je specialny bod a vela trojuholnikov.
  5.   Mame povedat, do ktorych z nich bod patri.
  6.   Realizovane cez vektorovy sucin (cross product)
  7. */
  8. #include<iostream>
  9. #include<algorithm>
  10.  
  11. using namespace std;
  12.  
  13. typedef pair<long long,long long> PLL;
  14. typedef pair<PLL,PLL> usecka;
  15.  
  16. #define MP make_pair 
  17.  
  18. //zaciatok = 0,0, vrati odpoved so znamienkom podla toho, ci je koniec1 nalavo od konca2
  19. long long cross(PLL koniec1, PLL koniec2){
  20.   return koniec1.first*koniec2.second - koniec1.second*koniec2.first;
  21. }
  22.  
  23. //poredpoklad: usecky v spravnom a jednotnom smere
  24. //trojuholnik A,B,C
  25. //u1: A->B, u2: B->C, u3: C->A
  26. bool vnutri(PLL bod, usecka u1, usecka u2, usecka u3){
  27.   PLL vektor1 = MP(u1.second.first - u1.first.first, u1.second.second - u1.first.second);
  28.   PLL vektor2 = MP(u2.second.first - u2.first.first, u2.second.second - u2.first.second);
  29.   PLL vektor3 = MP(u3.second.first - u3.first.first, u3.second.second - u3.first.second);
  30.   long long c1 = cross( vektor1, MP(bod.first - u1.first.first, bod.second - u1.first.second));
  31.   long long c2 = cross( vektor2, MP(bod.first - u2.first.first, bod.second - u2.first.second));
  32.   long long c3 = cross( vektor3, MP(bod.first - u3.first.first, bod.second - u3.first.second));
  33.   if (c1*c2 < 0) return false;
  34.   if (c1*c3 < 0) return false;
  35.   if (c2*c3 < 0) return false;
  36.   return true;
  37. }
  38.  
  39. int main(){
  40.   int x,y,K;
  41.   cin >> x >> y >> K;
  42.   PLL bod = MP(x,y);
  43.   int prvy = 1;
  44.   for(int i=0;i<K;i++){
  45.     int x1,x2,x3,y1,y2,y3;
  46.     cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
  47.     usecka u1 = MP( MP(x1,y1), MP(x2,y2));
  48.     usecka u2 = MP( MP(x2,y2), MP(x3,y3));
  49.     usecka u3 = MP( MP(x3,y3), MP(x1,y1));
  50.     if (vnutri(bod,u1,u2,u3)){
  51.       if (prvy == 0) cout << " ";
  52.       cout << (i+1);
  53.       prvy = 0;
  54.     }
  55.   }
  56.   cout << endl;
  57.   return 0;
  58. }
Time limit exceeded #stdin #stdout 5s 2728KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/nZEHB
language:
C++ (gcc 8.3)
created:
14 years ago
visibility:
public

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!