Advertisement
yungyao

tioj 1205

Mar 6th, 2021
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.62 KB | None | 0 0
  1. using namespace std;
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <utility>
  7. #include <bitset>
  8. #include <set>
  9. #include <string>
  10. #include <stack>
  11. #include <iomanip>
  12. #include <map>
  13.  
  14. #define pb push_back
  15. #define F first
  16. #define S second
  17. #define LL long long
  18. #define mid (LB+RB)/2
  19. #define iter(x) x.begin(),x.end()
  20.  
  21. /*
  22. 8e7 so dian
  23. FHVirus so dian
  24. youou so dian
  25. KYW so dian
  26. hubert so dian
  27. jass so dian
  28. tingyu so dian
  29. */
  30.  
  31. //IO
  32. #include <iostream>
  33. #define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
  34. #define endl '\n'
  35.  
  36. //workspace
  37.  
  38. #define pii pair<LL,LL>
  39.  
  40. inline LL cross (pii o,pii a,pii b){
  41. return (a.F - o.F) * (b.S - o.S) - (a.S - o.S) * (b.F - o.F);
  42. }
  43.  
  44. inline LL dot (pii o,pii a,pii b){
  45. return (a.F - o.F) * (b.F - o.F) + (a.S - o.S) * (b.S - o.S);
  46. }
  47.  
  48. pii vo;
  49. inline bool cmp(pii a,pii b){
  50. if ((a.S - vo.S < 0) ^ (b.S - vo.S < 0))
  51. return a.S - vo.S >= 0;
  52. return cross(vo,a,b) <= 0;
  53. }
  54.  
  55. inline void solve(int n){
  56. vector <pii> v;
  57. while (n--){
  58. int x,y;
  59.  
  60. cin >> x >> y;
  61. v.pb({x,y});
  62. }
  63. vector <pii> sorted = v;
  64.  
  65. int ans = 0;
  66. for (auto o:v){
  67. vo = o;
  68. sort (iter(sorted),cmp);
  69. vector <pair<pii,int>> it;
  70. bool exMinus = 0;
  71. if (sorted[0] != o)
  72. it.pb({sorted[0],1});
  73. else{
  74. it.pb({sorted[1],1});
  75. exMinus = 1;
  76. }
  77.  
  78. for (int i=(sorted[0] != o ? 1 : 2);i<sorted.size();++i){
  79. if (sorted[i] == o){
  80. exMinus = 1;
  81. continue;
  82. }
  83. if ((sorted[i-1] != o && cross(o,sorted[i-1],sorted[i])) || (exMinus && cross(o,sorted[i-2],sorted[i])))
  84. it.pb({sorted[i],1});
  85. else
  86. ++it[it.size()-1].S;
  87. exMinus = 0;
  88. }
  89.  
  90. for (int i=0,j=1;i<it.size();++i){
  91. //if (o.F == 0 && o.S == 1)
  92. //cout << it[i].F.F << ' ' << it[i].F.S << '\n';
  93. j = max(j,i+1);
  94. while (j+1 < i + it.size() && dot(o,it[i%it.size()].F,it[j%it.size()].F) > 0 && cross(o,it[i%it.size()].F,it[j%it.size()].F) < 0)
  95. ++j;
  96.  
  97. if (!dot(o,it[i%it.size()].F,it[j%it.size()].F) && cross(o,it[i%it.size()].F,it[j%it.size()].F) < 0)
  98. ans += it[i%it.size()].S * it[j%it.size()].S;
  99. }
  100. //cout << o.F << ',' << o.S << ' ' << it.size() << ' ' << ans << '\n';
  101. }
  102.  
  103. cout << ans << '\n';
  104. }
  105.  
  106. int main(){
  107. theyRSOOOOOOOOODIAN
  108. int n;
  109.  
  110. while (cin >> n && n) solve(n);
  111.  
  112. return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement