Analyzing Polyline — Codeforces Round #123 (Div. 2)

Question meaning: https://codeforc.es/problemset/problem/195/D

Find the number of polyline segments.

Thinking:

Sort pos, add k to different interval segments, and two dp handle different k>0 or k<0 prefixes, just judge.

Note: long double, ESP=1e-20.

 1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);

 2 #include //sprintf islower isupper

 3 #include //malloc exit strcat itoa system("cls")

 4 #include //pair

 5 #include //freopen("C:\Users\13606\Desktop\draft.txt","r",stdin);

 6 #include 

 7 //#include  8 //#include

 9 #include 

 10 #include 

 11 #include <set>

 12 #include <string.h>//strstr substr

 13 #include <string>

 14 #include //srand(((unsigned)time(NULL))); Seed n=rand()%10-0~9;

 15 #include 

 16 #include 

 17 #include //priority_queue, greater> q;//less

 18 #include //emplace_back

 19 //#include 

 20 //#include //reverse(a, a+len);// ~! ~! floor

 21 #include //sort + unique: sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)

 22 using  namespace std;//next_permutation(a+1,a+1+n); //prev_permutation

 23 #define fo(a,b,c) for(register int a=b;a<=c;++a)

 24 #define fr(a,b,c) for(register int a=b;a>=c;--a)

 25 #define mem(a,b) memset(a,b ,sizeof(a))

 26 #define pr printf

 27 #define sc scanf

 28 #define ls rt<<1

 29 #define rs rt<<1|1

 30 typedef long long ll;

 31 #define RG register int;

 32 void swapp(int &a,int &b);

 33 double fabss(double a);

 34 int maxx(int a,int b);

 35 int minn(int a,int b);

 36 int Del_bit_1(int n);

 37 int lowbit(int n);

 38 int abss(int a);

 39 //const long long INF=(1LL<<60);

 40 const  double E=2.718281828;

 41 const double PI=acos(-1.0);

 42 const int inf=(1<<30);

 43 const double ESP=1e-20;

 44 const int mod=(int)1e9+7;

 45 const int N=(int)1e6+10;

 46

 47 struct node

 48 {

 49 int k,b,id;

 50 long double pos;

 51 friend bool operator<(node ​​a,node b)

 52  {

 53 return a.pos<b.pos;

 54 }

 55 }a[N];

 56

 57 long  double get(int k,int b)

 58 {

 59 long double len=1.0*b/(1.0* k);

 60 len=abs(len);

 61 if(k>0)

 62  {

 63 if(b>0)

 64 return -len;

 65 else

 66 return len;

 67 }

 68 else

 69  {

 70 if(b>0)

 71 return len;

 72 else

 73 return -len;

 74 }

 75 }

 76 bool same(long double x,long double y)

 77 {

 78 return abs(xy)<ESP;

 79 }

 80

 81 ll dp[N],dp2[N];

 82

 83 int main()

 84 {

 85 int n,cnt=0;

 86 long double xx;

 87 sc("%d",&n);

 88 for(int i=1;i<=n;++i )

 89  {

 90 int k,b;

 91 sc("%d%d",&k,&b);

 92 if(k==0)

 93 continue;

 94 a[++cnt]={k,b},a[cnt].pos=get(a[cnt].k,a[cnt].b);

 95 }

 96 n=cnt;

 97 sort(a+1,a+1+n);

 98 a[1].id=1;

 99 int id=1;

100 for(int i=2;i<=n;++i )

101  {

102 if(!same(a[i] .pos,a[i-1].pos))

103 id++;

104 a[i].id=id;

105 }

106 for(int i=1;i<=n;++i )

107 if(a[i].k> 0)

108 dp[a[i].id]+=a[ i].k;

109 for(int i=1;i<=n;++i )

110 dp[i]+=dp[i-1 span>];

111 for(int i=n;i>=1;--i )

112  {

113 if(a[i].k< 0)

114 dp2[a[i].id-1]+=a[i].k;

115 }

116 for(int i=n;i>=0;--i )

117 dp2[i]+=dp2[i+1];

118 int ans=0;

119 for(int i=1;i<=id;++i )

120 if(dp[i]+dp2[ i]!=dp[i-1]+dp2[i-1])

121 ans++;

122 pr("%d
",ans);

123 return 0;

124 }

125

126 /************************************************** ************************************/

127

128 int maxx(int a,int b)

129 {

130 return a>b?a:b;

131 }

132

133 void swapp(int &a,int &b)

134 {

135 a^=b^=a^=b;

136 }

137

138 int lowbit(int n)

139 {

140 return n&(-n);

141 }

142

143 int Del_bit_1(int n)

144 {

145 return n&(n-1);

146 }

147

148 int abss(int a)

149 {

150 return a>0?a:-a;

151 }

152

153 double fabss(double a)

154 {

155 return a>0?a:-a;

156 }

157

158 int minn(int a,int b)

159 {

160 return aa:b;

161 }

 1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);

 2 #include //sprintf islower isupper

 3 #include //malloc exit strcat itoa system("cls")

 4 #include //pair

 5 #include //freopen("C:\Users\13606\Desktop\draft.txt","r",stdin);

 6 #include 

 7 //#include  8 //#include

 9 #include 

 10 #include 

 11 #include <set>

 12 #include <string.h>//strstr substr

 13 #include <string>

 14 #include //srand(((unsigned)time(NULL))); Seed n=rand()%10-0~9;

 15 #include 

 16 #include 

 17 #include //priority_queue, greater> q;//less

 18 #include //emplace_back

 19 //#include 

 20 //#include //reverse(a, a+len);// ~! ~! floor

 21 #include //sort + unique: sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)

 22 using  namespace std;//next_permutation(a+1,a+1+n); //prev_permutation

 23 #define fo(a,b,c) for(register int a=b;a<=c;++a)

 24 #define fr(a,b,c) for(register int a=b;a>=c;--a)

 25 #define mem(a,b) memset(a,b ,sizeof(a))

 26 #define pr printf

 27 #define sc scanf

 28 #define ls rt<<1

 29 #define rs rt<<1|1

 30 typedef long long ll;

 31 #define RG register int;

 32 void swapp(int &a,int &b);

 33 double fabss(double a);

 34 int maxx(int a,int b);

 35 int minn(int a,int b);

 36 int Del_bit_1(int n);

 37 int lowbit(int n);

 38 int abss(int a);

 39 //const long long INF=(1LL<<60);

 40 const  double E=2.718281828;

 41 const double PI=acos(-1.0);

 42 const int inf=(1<<30);

 43 const double ESP=1e-20;

 44 const int mod=(int)1e9+7;

 45 const int N=(int)1e6+10;

 46

 47 struct node

 48 {

 49     int k,b,id;

 50     long double pos;

 51     friend bool operator<(node a,node b)

 52     {

 53         return a.pos<b.pos;

 54     }

 55 }a[N];

 56 

 57 long double get(int k,int b)

 58 {

 59     long double len=1.0*b/(1.0*k);

 60     len=abs(len);

 61     if(k>0)

 62     {

 63         if(b>0)

 64             return -len;

 65         else

 66             return len;

 67     }

 68     else

 69     {

 70         if(b>0)

 71             return len;

 72         else

 73             return -len;

 74     }

 75 }

 76 bool same(long double x,long double y)

 77 {

 78     return abs(x-y)<ESP;

 79 }

 80 

 81 ll dp[N],dp2[N];

 82 

 83 int main()

 84 {

 85     int n,cnt=0;

 86     long double xx;

 87     sc("%d",&n);

 88     for(int i=1;i<=n;++i)

 89     {

 90         int k,b;

 91         sc("%d%d",&k,&b);

 92         if(k==0)

 93             continue;

 94         a[++cnt]={k,b},a[cnt].pos=get(a[cnt].k,a[cnt].b);

 95     }

 96     n=cnt;

 97     sort(a+1,a+1+n);

 98     a[1].id=1;

 99     int id=1;

100     for(int i=2;i<=n;++i)

101     {

102         if(!same(a[i].pos,a[i-1].pos))

103             id++;

104         a[i].id=id;

105     }

106     for(int i=1;i<=n;++i)

107         if(a[i].k>0)

108             dp[a[i].id]+=a[i].k;

109     for(int i=1;i<=n;++i)

110         dp[i]+=dp[i-1];

111     for(int i=n;i>=1;--i)

112     {

113         if(a[i].k<0)

114             dp2[a[i].id-1]+=a[i].k;

115     }

116     for(int i=n;i>=0;--i)

117         dp2[i]+=dp2[i+1];

118     int ans=0;

119     for(int i=1;i<=id;++i)

120         if(dp[i]+dp2[i]!=dp[i-1]+dp2[i-1])

121             ans++;

122     pr("%d
",ans);

123     return 0;

124 }

125 

126 /**************************************************************************************/

127 

128 int maxx(int a,int b)

129 {

130     return a>b?a:b;

131 }

132 

133 void swapp(int &a,int &b)

134 {

135     a^=b^=a^=b;

136 }

137 

138 int lowbit(int n)

139 {

140     return n&(-n);

141 }

142 

143 int Del_bit_1(int n)

144 {

145     return n&(n-1);

146 }

147 

148 int abss(int a)

149 {

150     return a>0?a:-a;

151 }

152 

153 double fabss(double a)

154 {

155     return a>0?a:-a;

156 }

157 

158 int minn(int a,int b)

159 {

160     return aa:b;

161 }