Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <fstream>
- #include <sstream>
- #include <cstdlib>
- #include <cstdio>
- #include <cctype>
- #include <ctime>
- #include <cmath>
- #include <memory>
- #include <cstring>
- #include <utility>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <vector>
- #include <string>
- using namespace std;
- typedef long long int LL;
- typedef long double LD;
- typedef vector<int> VI;
- typedef vector<VI> VVI;
- typedef vector<bool> VB;
- typedef vector<VB> VVB;
- typedef vector<string> VS;
- typedef set<int> SI;
- typedef map<int,int> MII;
- typedef pair<int,int> II;
- typedef vector<II> VII;
- typedef vector<VII> VVII;
- typedef vector<LL> VL;
- typedef vector<VL> VLL;
- typedef set<LL> SL;
- typedef map<LL,LL> MLL;
- typedef pair<LL,LL> LLL;
- typedef vector<LD> VD;
- typedef vector<VD> VVD;
- template<typename T>
- inline T sqr(const T &a){return a*a;}
- template<typename T>
- inline int nread(vector<T> &a)
- {
- int n;
- cin >> n;
- a.clear();
- a.resize(n);
- for (int i=0;i<n;i++) cin >> a[i];
- return n;
- }
- #define TASKNAME "a"
- struct P {
- LL x,y;
- P(LL x=0,LL y=0): x(x),y(y) {}
- };
- P operator-(P a,P b) {
- return P(a.x-b.x,a.y-b.y);
- }
- P work;
- vector<P> flam;
- int ss;
- int n,m;
- LL operator*(P a,P b) {
- return a.x*b.y-a.y*b.x;
- }
- double ang(P a) {
- return atan2((a-work).y,(a-work).x);
- }
- bool lsw0(int a, int b) {
- if (a==0 || b==0) cout << "Fail" << endl;
- return ang(flam[a]) < ang(flam[b]);
- }
- void check() {
- vector<int> perm;
- for (int j=1;j<m;j++) {
- perm.push_back(j);
- }
- work = flam[0];
- ss=0;
- sort(perm.begin(),perm.end(),lsw0);
- }
- bool ls(int a, int b) {
- return ang(flam[a]) < ang(flam[b]);
- }
- int main () {
- // freopen(TASKNAME".in","r",stdin);
- // freopen(TASKNAME".out","w",stdout);
- cin >> n >> m;
- flam.assign(m,P());
- for (int i=0;i<m;i++) {
- cin >> flam[i].x >> flam[i].y;
- }
- check();
- vector<int> best(n,1);
- for (int s=0;s<m;s++) {
- vector<int> perm;
- for (int j=0;j<m;j++) {
- if (j!=s) perm.push_back(j);
- }
- work = flam[s];
- ss=s;
- stable_sort(perm.begin(),perm.end(),ls);
- perm.insert(perm.end(), perm.begin(),perm.end());
- for (int i=0;i<perm.size();) {
- int j;
- for (j=i+1;j<perm.size();j++) {
- if ((flam[perm[i]]-work)*(flam[perm[j]]-work)!=0) break;
- }
- if (work.y==flam[perm[i]].y) {i=j;continue;}
- if ((flam[perm[i]].x-work.x)*flam[perm[i]].y%(work.y-flam[perm[i]].y)==0) {
- LL k = flam[perm[i]].x+(flam[perm[i]].x-work.x)*flam[perm[i]].y/(work.y-flam[perm[i]].y)-1;
- if (k>=0 && k<n) best[k]=max(best[k],min(j-i+1,m));
- }
- i=j;
- }
- }
- LL res=0;
- for (int i=0;i<n;i++) {
- res+=best[i];
- }
- cout << res << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment