fork download
copy 
  1. /* Author haleyk10198 */
  2. /* 作者:  haleyk10198 */
  3. #include <iostream>
  4. #include <fstream>
  5. #include <sstream>
  6. #include <cstdlib>
  7. #include <cstdio>
  8. #include <vector>
  9. #include <map>
  10. #include <queue>
  11. #include <cmath>
  12. #include <algorithm>
  13. #include <cstring>
  14. #include <iomanip>
  15. #include <ctime>
  16. #include <string>
  17. #include <set>
  18.  
  19. #define MOD 1000000007
  20. #define INF 2147483647
  21. #define PI 3.1415926535897932384626433
  22. #define ll long long
  23. #define pii pair<int,int>
  24. #define mp(x,y) make_pair((x),(y))
  25.  
  26. using namespace std;
  27.  
  28. pii pos[10];
  29. pii mon[1010];
  30. pii now;
  31. int nowa;
  32. vector<vector<int> > srt;
  33. bool hit[1010];
  34. vector<pii> delay;
  35.  
  36. double angle(pii a,pii b){
  37. 	if(a.first==b.first){
  38. 		if(a.second>b.second)
  39. 			return -90.0;
  40. 		else
  41. 			return 90.0;
  42. 	}
  43. 	if(a.first>b.first)
  44. 		return tan(1.0*(b.second-a.second)/(b.first-a.first));
  45. 	else
  46. 		return PI+tan(1.0*(b.second-a.second)/(b.first-a.first));
  47. }
  48.  
  49. ll dist(pii a,pii b){
  50. 	return abs(1LL*a.first-b.first)+abs(1LL*a.second-b.second);
  51. }
  52.  
  53. struct Custom{
  54. 	bool operator()(int a,int b){
  55. 		pii mona=mon[srt[nowa][a]],monb=mon[srt[nowa][b]];
  56. 		return (angle(now,mona)<angle(now,monb))||(angle(now,mona)==angle(now,monb)&&dist(now,mona)<dist(now,monb));
  57. 	}
  58. };
  59.  
  60. int main(){
  61. 	int n,k;
  62. 	cin>>k>>n;
  63. 	for(int i=0;i<k;i++)
  64. 		cin>>pos[i].first>>pos[i].second;
  65. 	for(int i=0;i<n;i++)
  66. 		cin>>mon[i].first>>mon[i].second;
  67. 	vector<int> dummy;
  68. 	for(int i=0;i<n;i++)
  69. 		dummy.push_back(i);
  70. 	for(int i=0;i<k;i++){
  71. 		srt.push_back(dummy);
  72. 		now=pos[i];
  73. 		nowa=i;
  74. 		sort(srt[i].begin(),srt[i].end(),Custom());
  75. 	}
  76. 	for(int round=0;round<k;round++){
  77. 		for(int i=0;i<k;i++){
  78. 			delay.clear();
  79. 			for(auto x:srt[i])
  80. 				cout<<angle(pos[i],mon[x])<<" "<<dist(pos[i],mon[x])<<endl;
  81. 			for(int j=0;j<srt[i].size();j++){
  82. 				if(j==0||angle(pos[i],mon[srt[i][j]])!=angle(pos[i],mon[srt[i][j-1]])){
  83. 					hit[srt[i][j]]=true;
  84. 					delay.push_back(mp(i,srt[i][j]));
  85. 				}
  86. 			}
  87. 		}
  88. 		for(auto x:delay){
  89. 			for(int i=0;i<k;i++){
  90. 				if(i-x.first){
  91. 					for(vector<int>::iterator it=srt[i].begin();it!=srt[i].end();it++){
  92. 						if(*it==x.second){
  93. 							srt[i].erase(it);
  94. 							break;
  95. 						}
  96. 					}
  97. 				}
  98. 			}
  99. 		}
  100. 	}
  101. 	int res=0;
  102. 	for(int i=0;i<n;i++)
  103. 		res+=hit[i];
  104. 	cout<<res<<endl;
  105. 	return 0;
  106. }
  107.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
3 8
10 20
0 0
20 40
300 600
30 60
170 340
50 100
28 56
90 180
-4 -8
-1 -2
stdout
copy 
-2.18504 33
-2.18504 42
0.956553 240
0.956553 54
0.956553 120
0.956553 480
0.956553 60
0.956553 870
-2.18504 3
-2.18504 12
0.956553 270
0.956553 84
0.956553 150
0.956553 510
0.956553 90
0.956553 900
-2.18504 63
-2.18504 72
0.956553 210
0.956553 24
0.956553 90
0.956553 450
0.956553 30
0.956553 840
-2.18504 42
0.956553 54
0.956553 120
0.956553 480
0.956553 60
0.956553 870
-2.18504 12
0.956553 84
0.956553 150
0.956553 510
0.956553 90
0.956553 900
-2.18504 63
-2.18504 72
0.956553 210
0.956553 24
0.956553 90
0.956553 450
0.956553 30
0.956553 840
-2.18504 42
0.956553 54
0.956553 120
0.956553 480
0.956553 60
0.956553 870
-2.18504 12
0.956553 84
0.956553 150
0.956553 510
0.956553 90
0.956553 900
-2.18504 63
-2.18504 72
0.956553 210
0.956553 24
0.956553 90
0.956553 450
0.956553 30
0.956553 840
4
https://ideone.com/1nht37
language:
C++14 (gcc 8.3)
created:
7 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!