当前位置：网站首页>[极角排序扫描法]UVa1606 - Amphiphilic Carbon Molecules

[极角排序扫描法]UVa1606 - Amphiphilic Carbon Molecules

2022-08-05 15:34:00 【51CTO】

       
       #include<bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       struct 
       
       Node{
       
       public :
       
       int 
       
       x,
       
       y,
       
       z;
       
       double 
       
       rad;
       
       bool 
       
       operator 
       
       < (
       
       const 
       
       Node
       
       & 
       
       rhs) 
       
       const {
       
       return 
       
       rad 
       
       < 
       
       rhs.
       
       rad;
       
    }
       
}
       
       c[
       
       1000],
       
       d[
       
       1000];
       
       bool 
       
       Turn(
       
       Node
       
       &
       
       a,
       
       Node
       
       &
       
       b)
       
{
       
       return 
       
       a.
       
       x
       
       *
       
       b.
       
       y
       
       >=
       
       a.
       
       y
       
       *
       
       b.
       
       x;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       N;
       
       while(
       
       ~scanf(
       
       "%d",
       
       &
       
       N)
       
       &&
       
       N){
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       N;
       
       i
       
       ++) 
       
       scanf(
       
       "%d%d%d",
       
       &
       
       c[
       
       i].
       
       x,
       
       &
       
       c[
       
       i].
       
       y,
       
       &
       
       c[
       
       i].
       
       z);
       
       if(
       
       N
       
       <=
       
       2) { 
       
       printf(
       
       "%d\n",
       
       N); 
       
       continue; }
       
       int 
       
       maxn
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       N;
       
       i
       
       ++){
       
       int 
       
       k
       
       =
       
       0;
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       N;
       
       j
       
       ++){
       
       if(
       
       i
       
       !=
       
       j){
       
       d[
       
       k].
       
       x 
       
       = 
       
       c[
       
       j].
       
       x
       
       -
       
       c[
       
       i].
       
       x;
       
       d[
       
       k].
       
       y 
       
       = 
       
       c[
       
       j].
       
       y
       
       -
       
       c[
       
       i].
       
       y;
       
       if(
       
       c[
       
       j].
       
       z){
       
       d[
       
       k].
       
       x 
       
       = 
       
       -
       
       d[
       
       k].
       
       x;
       
       d[
       
       k].
       
       y 
       
       = 
       
       -
       
       d[
       
       k].
       
       y;
       
                    }
       
       d[
       
       k].
       
       rad 
       
       = 
       
       atan2(
       
       d[
       
       k].
       
       y,
       
       d[
       
       k].
       
       x);
       
       k
       
       ++;
       
                }
       
            }
       
       sort(
       
       d,
       
       d
       
       +
       
       k);
       
       int 
       
       L
       
       =
       
       0;
       
       int 
       
       ans
       
       =
       
       1;
       
       int 
       
       R
       
       =
       
       0;
       
       while(
       
       L
       
       <
       
       k){
       
       if(
       
       L
       
       ==
       
       R){
       
       R
       
       =(
       
       R
       
       +
       
       1)
       
       %
       
       k; 
       
       ans
       
       ++;
       
                }
       
       while(
       
       L
       
       !=
       
       R
       
       &&
       
       Turn(
       
       d[
       
       L],
       
       d[
       
       R])){
       
       ans
       
       ++; 
       
       R
       
       =(
       
       R
       
       +
       
       1)
       
       %
       
       k;
       
                }
       
       maxn 
       
       = 
       
       max(
       
       maxn,
       
       ans); 
       
       L
       
       ++; 
       
       ans
       
       --;
       
            }
       
        }
       
       printf(
       
       "%d\n",
       
       maxn);
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.