NC15751. 零点
描述
OI 的生涯如此短暂，恐怕就要到了分别的时候了。
回想起自己的OI 生活，那一切的一切都历历在目。
仍然记得，在骄阳似火的夏天，机房内一群完全不懂编程的小白，围在黑板前，听学长不厌其烦的讲解。
仍然记得，在金凤飒爽的秋天，考完NOIP时那失望的表情，那下定决心努力补弱的意志。
仍然记得，在白雪皑皑的冬天，靠在机房暖气边，整理着一份又一份的笔记，修改了一道又一道题目。
仍然记得，那些来自五湖四海的朋友们，那一场又一场的比赛，那一次又一次的集训。
尽管依依不舍，尽管不愿分别，可是——终于，要告别了吗？
带着一颗热爱程序设计竞赛的心，祝愿自己能够与那个她共同考上理想的大学，祝大家能在这算法竞赛中，欣赏到美丽的风景，认识到志同道合的朋友们，达到自己想达到的高度，不断挑战自我，不断砥砺前行！
THE END —— Johnson
输入描述
第一行：一个整数n。
接下来n行：每行两个整数xi , yi。
输出描述
将零点的数量记为cnt。
若cnt > 3 * 105，则：
第一行：一个整数-1。
否则：
第一行：一个整数cnt。第二行：cnt个整数，表示整数零点的横坐标，用空格隔开（如果cnt为0，则第二行不必输出）。
示例1
输入:
2 -1 -1 1 1
输出:
1 0
示例2
输入:
4 -2 -2 0 2 1 -2 2 -1
输出:
2 -1 3
C++(clang++11) 解法, 执行用时: 150ms, 内存消耗: 14720K, 提交时间: 2021-03-12 16:10:14
#include<bits/stdc++.h>
using namespace std;
long long Z[300005],X[700005],Y[700005];
int main()
{
long long i,j,s=0,n;
double x;
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld%lld",&X[i],&Y[i]);
if(!Y[1]&&!Y[2])s=300005;
else {
x=1;
x=X[1]-x*Y[1]*(X[2]-X[1])/(Y[2]-Y[1]),j=x;
if(x-j==0&&j<X[2])Z[s++]=j;
}
for(i=3;s<=300000&&i<n;i++){
if(!Y[i-1]&&!Y[i])for(j=X[i-1];s<=300000&&j<X[i];j++)Z[s++]=j;
else if(!Y[i-1]&&Y[i])Z[s++]=X[i-1];
else if(Y[i-1]*Y[i]<0)
{
x=1;
x=X[i-1]-x*Y[i-1]*(X[i]-X[i-1])/(Y[i]-Y[i-1]),j=x;
if(x-j==0)Z[s++]=j;
}
}
if(!Y[n-1]&&!Y[n])s=300005;
else
{
x=1;
x=X[n-1]-x*Y[n-1]*(X[n]-X[n-1])/(Y[n]-Y[n-1]),j=x;
if(x-j==0&&j>=X[n-1]&&(s&&j!=Z[s-1]||!s))Z[s++]=j;
}
if(s>300000)printf("-1\n");
else {
printf("%lld\n",s);
for(i=0;i<s;i++)
{
if(i)printf(" ");
printf("%lld",Z[i]);
}
}
return 0;
}